lld: Propeller framework part I

[shenhan]

Summary

Hi reviewers, this is a split version of the CL - https://reviews.llvm.org/D68062 which seems too big to review and submit in one shot.

What does this CL include:

1. added Propeller config class PropellerConfig.h
2. added interface to lld driver in LinkerPropeller.c/cpp.
3. propeller flags handling

This CL is self-contained, buildable and non-functional. all real work is done in the origin https://reviews.llvm.org/D68062

[MaskRay]

The variable naming does not follow lld's convention (lowerCase).

lld/ELF/Propeller/PropellerConfig.h

13

lld/Common/LLVM.h pulls in declarations of common utilities. No need for using llvm::StringRef.

lld/include/lld/Common/PropellerCommon.h

18

Prefer []

29

excess empty line

47

Prefer lowerCased variable names.

83

Rationale? Do you have a concrete example this rule is needed?

96

Drop unnecessary this

153

if (s1 && s2)
  return s1->ordinal < s2->ordinal;
return !!s1 < !!s2;

[shenhan]

Hi Markray, thanks for the review.

[shenhan]

lld/include/lld/Common/PropellerCommon.h

47

I'll address this later, cause this changes almost every other file.

83

Yeah, we see zero-sized basic block symbol at the end of a function.

[shenhan]

Fixed all variable names to comply with lld naming convention.

[ruiu]

As we discussed today, this patch didn't make sense to me at first sight, as it redoes a lot of things that we already implemented to lld (e.g. making a new "config" object only for this thing, defining a new type of Symbol (SymbolEntry) even though we have Symbol class, etc.) But the thing is that this code is intended to be used by some external tool. If that's the case, you should consider moving this to LLVM instead and use the code from lld and your tool.

[shenhan]

Thanks Rui. Uploaded the patch: 1) removed PropellerConfig 2). Removed PropellerCommon.h from patch (and moved it into llvm realm).

[shenhan]

Hi, would you to take another look? Thanks, -Han

lld/ELF/CMakeLists.txt

add_lld_library(lldELF
   DWARF.cpp
   Driver.cpp
   DriverUtils.cpp
   EhFrame.cpp
   ICF.cpp
   InputFiles.cpp
   InputSection.cpp
   LTO.cpp
+  LinkerPropeller.cpp
   LinkerScript.cpp
   MapFile.cpp
   MarkLive.cpp
   OutputSections.cpp
   Relocations.cpp
   ScriptLexer.cpp
   ScriptParser.cpp
   SymbolTable.cpp

lld/ELF/Config.h

struct Configuration {
   llvm::StringRef ltoObjPath;
   llvm::StringRef ltoSampleProfile;
   llvm::StringRef mapFile;
   llvm::StringRef outputFile;
   llvm::StringRef optRemarksFilename;
   llvm::StringRef optRemarksPasses;
   llvm::StringRef optRemarksFormat;
   llvm::StringRef progName;
+  llvm::StringRef propeller;
+  llvm::StringRef propellerDumpSymbolOrder;
+  uint64_t propellerFallthroughWeight;
+  uint64_t propellerForwardJumpWeight;
+  uint64_t propellerBackwardJumpWeight;
+  uint64_t propellerClusterMergeSizeThreshold;
+  uint64_t propellerForwardJumpDistance;
+  uint64_t propellerBackwardJumpDistance;
+  uint64_t propellerChainSplitThreshold;
+  std::vector<llvm::StringRef> propellerDumpCfgs;
+  std::vector<llvm::StringRef> propellerDebugSymbols;
+  std::vector<llvm::StringRef> propellerOpts;
   llvm::StringRef printSymbolOrder;
   llvm::StringRef soName;
   llvm::StringRef sysroot;
   llvm::StringRef thinLTOCacheDir;
   llvm::StringRef thinLTOIndexOnlyArg;
+  llvm::StringRef ltoBBSections;
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOObjectSuffixReplace;
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOPrefixReplace;
   std::string rpath;
   std::vector<VersionDefinition> versionDefinitions;
   std::vector<llvm::StringRef> auxiliaryList;
   std::vector<llvm::StringRef> filterList;
   std::vector<llvm::StringRef> searchPaths;
   std::vector<llvm::StringRef> symbolOrderingFile;
struct Configuration {
   bool gnuUnique;
   bool hasDynamicList = false;
   bool hasDynSymTab;
   bool ignoreDataAddressEquality;
   bool ignoreFunctionAddressEquality;
   bool ltoCSProfileGenerate;
   bool ltoDebugPassManager;
   bool ltoNewPassManager;
+  bool ltoUniqueBBSectionNames;
   bool mergeArmExidx;
   bool mipsN32Abi = false;
   bool mmapOutputFile;
   bool nmagic;
   bool noinhibitExec;
   bool nostdlib;
   bool oFormatBinary;
   bool omagic;
+  bool optimizeBBJumps;
   bool optRemarksWithHotness;
   bool pacPlt;
   bool picThunk;
   bool pie;
   bool printGcSections;
   bool printIcfSections;
+  bool propellerKeepNamedSymbols;
+  bool propellerPrintStats;
+  bool propellerReorderIP = false;
+  bool propellerReorderBlocks;
+  bool propellerReorderFuncs;
+  bool propellerSplitFuncs;
   bool relocatable;
   bool relrPackDynRelocs;
   bool saveTemps;
   bool singleRoRx;
   bool shared;
+  bool shrinkJumpsAggressively;
   bool isStatic = false;
   bool sysvHash = false;
   bool target1Rel;
   bool trace;
   bool thinLTOEmitImportsFiles;
   bool thinLTOIndexOnly;
   bool tocOptimize;
   bool undefinedVersion;

lld/ELF/Driver.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
 #include "ICF.h"
 #include "InputFiles.h"
 #include "InputSection.h"
+#include "LinkerPropeller.h"
 #include "LinkerScript.h"
 #include "MarkLive.h"
 #include "OutputSections.h"
 #include "ScriptParser.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
   for (InputFile *f : objectFiles)
     for (InputSectionBase *s : f->getSections())
       if (s && s != &InputSection::discarded)
         inputSections.push_back(s);
   for (BinaryFile *f : binaryFiles)
     for (InputSectionBase *s : f->getSections())
       inputSections.push_back(cast<InputSection>(s));
 
+  lld::propeller::doPropeller();
+
   llvm::erase_if(inputSections, [](InputSectionBase *s) {
     if (s->type == SHT_LLVM_SYMPART) {
       readSymbolPartitionSection<ELFT>(s);
       return true;
     }
 
     // We do not want to emit debug sections if --strip-all
     // or -strip-debug are given.

lld/ELF/LinkerPropeller.h

+//===- LinkerPropeller.h ----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This is the interface between LLD/ELF and Propeller. All interactions
+// between LLD/ELF and propeller must be defined here.
+//
+// All dependencies on lld/ELF/*.h must happen in this file and
+// LinkerPropeller.cpp.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_LINKER_PROPELLER_H
+#define LLD_ELF_LINKER_PROPELLER_H
+
+#include "llvm/ADT/StringRef.h"
+
+namespace lld {
+namespace propeller {
+// Propeller interface to lld.
+void doPropeller();
+
+// Returns true if this is a BB symbol and shall be kept in the final binary's
+// strtab.
+bool isBBSymbolAndKeepIt(llvm::StringRef N);
+} // namespace propeller
+} // namespace lld
+
+#endif

lld/ELF/LinkerPropeller.cpp

+//===- 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<lld::elf::InputFile> into vector<lld::propeller::ObjectView>.
+//
+// "doPropeller" then passes PropellerConfig and vector<ObjectView> to Propeller
+// instance, and finally, after Propeller is done with its work, doPropeller
+// passes the resulting symboll ordering back to lld.
+//
+// In summary, the dependencies of Propeller are:
+//   - a set of "lld::elf::InputFile"s.
+//   - command line arguments in lld::elf::Config
+//   - lld's being able to arrange section orders according to a vector of
+//     symbol names.
+//
+// All lld/ELF/Propeller/* only uses headers from lld/include, and llvm/include.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LinkerPropeller.h"
+
+#include "Config.h"
+#include "Propeller/PropellerConfig.h"
+
+namespace lld {
+
+using elf::config;
+
+namespace propeller {
+
+// Set up PropellerConfig from global lld config instnace.
+static void setupConfig() {
+  propellerConfig.optPropeller = config->propeller;
+  propellerConfig.optLinkerOutputFile = config->outputFile;
+
+#define COPY_CONFIG(NAME) propellerConfig.opt##NAME = config->propeller##NAME
+  COPY_CONFIG(BackwardJumpDistance);
+  COPY_CONFIG(BackwardJumpWeight);
+  COPY_CONFIG(ChainSplitThreshold);
+  COPY_CONFIG(ClusterMergeSizeThreshold);
+  COPY_CONFIG(DebugSymbols);
+  COPY_CONFIG(DumpCfgs);
+  COPY_CONFIG(DumpSymbolOrder);
+  COPY_CONFIG(FallthroughWeight);
+  COPY_CONFIG(ForwardJumpDistance);
+  COPY_CONFIG(ForwardJumpWeight);
+  COPY_CONFIG(KeepNamedSymbols);
+  COPY_CONFIG(Opts);
+  COPY_CONFIG(PrintStats);
+  COPY_CONFIG(ReorderBlocks);
+  COPY_CONFIG(ReorderFuncs);
+  COPY_CONFIG(ReorderIP);
+  COPY_CONFIG(SplitFuncs);
+#undef COPY_CONFIG
+
+  // Scale weights for use in the computation of ExtTSP score.
+  propellerConfig.optFallthroughWeight *=
+      propellerConfig.optForwardJumpDistance *
+      propellerConfig.optBackwardJumpDistance;
+  propellerConfig.optBackwardJumpWeight *=
+      propellerConfig.optForwardJumpDistance;
+  propellerConfig.optForwardJumpWeight *=
+      propellerConfig.optBackwardJumpDistance;
+}
+
+// Propeller framework entrance.
+void doPropeller() {
+  if (config->propeller.empty())
+    return;
+
+  setupConfig();
+
+  // Propeller work starts here. In next CL.
+
+  // prop = make<Propeller>();
+  // ...
+  // ...
+  // ...
+}
+
+bool isBBSymbolAndKeepIt(llvm::StringRef name) {
+  // Real work done in next CL.
+  return false;
+}
+
+PropellerConfig propellerConfig;
+} // namespace propeller
+} // namespace lld

lld/ELF/Propeller/PropellerConfig.h

+//===-------------------- PropellerConfig.h -------------------------------===//
+//
+
+#ifndef LLD_ELF_PROPELLER_CONFIG_H
+#define LLD_ELF_PROPELLER_CONFIG_H
+
+#include "llvm/ADT/StringRef.h"
+
+#include <string>
+#include <vector>
+
+namespace lld {
+namespace propeller {
+
+struct PropellerConfig {
+  uint64_t optBackwardJumpDistance;
+  uint64_t optBackwardJumpWeight;
+  uint64_t optChainSplitThreshold;
+  std::vector<llvm::StringRef> optDebugSymbols;
+  std::vector<llvm::StringRef> optDumpCfgs;
+  uint64_t optClusterMergeSizeThreshold;
+  StringRef optDumpSymbolOrder;
+  uint64_t optFallthroughWeight;
+  uint64_t optForwardJumpDistance;
+  uint64_t optForwardJumpWeight;
+  bool optKeepNamedSymbols;
+  StringRef optLinkerOutputFile;
+  std::vector<llvm::StringRef> optOpts;
+  bool optPrintStats;
+  StringRef optPropeller;
+  bool optReorderBlocks;
+  bool optReorderFuncs;
+  bool optSplitFuncs;
+  bool optReorderIP;
+};
+
+extern PropellerConfig propellerConfig;
+
+} // namespace propeller
+} // namespace lld
+
+#endif

lld/include/lld/Common/PropellerCommon.h

+#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 <string>
+
+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<StringRef, 3>;
+
+  SymbolEntry(uint64_t O, const StringRef &N, AliasesTy &&As, uint64_t A,
+              uint64_t S, uint8_t T, bool BB = false,
+              SymbolEntry *FuncPtr = nullptr)
+      : Ordinal(O), Name(N), Aliases(As), Addr(A), Size(S), Type(T), BBTag(BB),
+        BBTagType(BB_NONE), HotTag(false), ContainingFunc(FuncPtr) {}
+
+  // Unique index number across all symbols that participate linking.
+  uint64_t Ordinal;
+  // For a function symbol, it's the full name. For a bb symbol this is only the
+  // bbindex part, which is the number of "a"s before the ".bb." part. For
+  // example "8", "10", etc. Refer to Propfile::createFunctionSymbol and
+  // Propfile::createBasicBlockSymbol.
+  StringRef Name;
+  // Only valid for function (BBTag == false) symbols. And aliases[0] always
+  // equals to Name. For example, SymbolEntry.Name = "foo", SymbolEntry.Aliases
+  // = {"foo", "foo2", "foo3"}.
+  AliasesTy Aliases;
+  uint64_t Addr;
+  uint64_t Size;
+  uint8_t Type; // Of type: llvm::objet::SymbolRef::Type.
+  bool BBTag;   // Whether this is a basic block section symbol.
+  BBTagTypeEnum BBTagType;
+
+  bool HotTag; // Whether this symbol is listed in the propeller section.
+  // For BBTag symbols, this is the containing fuction pointer, for a normal
+  // function symbol, this points to itself. This is neverl nullptr.
+  SymbolEntry *ContainingFunc;
+
+  bool isReturnBlock() const {
+    return BBTagType == BB_RETURN || BBTagType == BB_RETURN_AND_LANDING_PAD;
+  }
+
+  bool isLandingPadBlock() const {
+    return BBTagType == BB_LANDING_PAD ||
+           BBTagType == BB_RETURN_AND_LANDING_PAD;
+  }
+
+  bool operator<(const SymbolEntry &Other) const {
+    return this->Ordinal < Other.Ordinal;
+  }
+
+  bool isFunction() const {
+    return Type == llvm::object::SymbolRef::ST_Function;
+  }
+
+  // Return true if "SymName" is a BB symbol, e.g., in the form of
+  // "a.BB.funcname", and set FuncName to the part after ".BB.", BBIndex to
+  // before ".BB.", if the pointers are nonnull.
+  static bool isBBSymbol(const StringRef &SymName,
+                         StringRef *FuncName = nullptr,
+                         StringRef *BBIndex = nullptr) {
+    if (SymName.empty())
+      return false;
+    auto R = SymName.split(BASIC_BLOCK_SEPARATOR);
+    if (R.second.empty())
+      return false;
+    for (auto *I = R.first.bytes_begin(), *J = R.first.bytes_end(); I != J; ++I)
+      if (strchr(BASIC_BLOCK_UNIFIED_CHARACTERS, *I) == NULL)
+        return false;
+    if (FuncName)
+      *FuncName = R.second;
+    if (BBIndex)
+      *BBIndex = R.first;
+    return true;
+  }
+
+  static BBTagTypeEnum toBBTagType(const char c) {
+    switch (c) {
+    case 'a':
+      return BB_NORMAL;
+    case 'r':
+      return BB_RETURN;
+    case 'l':
+      return BB_LANDING_PAD;
+    case 'L':
+      return BB_RETURN_AND_LANDING_PAD;
+    default:
+      assert(false);
+    }
+    return BB_NONE;
+  }
+
+  static const uint64_t INVALID_ADDRESS = uint64_t(-1);
+};
+
+struct SymbolEntryOrdinalLessComparator {
+  bool operator()(SymbolEntry *s1, SymbolEntry *s2) const {
+    if (s1 && s2)
+      return s1->Ordinal < s2->Ordinal;
+    return !!s1 < !!s2;
+  }
+};
+
+} // namespace propeller
+} // namespace lld
+#endif