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 propellerBBOrderFile;
+  std::vector<llvm::StringRef> propellerBBOrder;
+  llvm::StringRef propellerDumpSymbolOrder;
+  double propellerFallthroughWeight;
+  double propellerForwardJumpWeight;
+  double propellerBackwardJumpWeight;
+  uint64_t propellerClusterMergeSizeThreshold;
+  uint64_t propellerForwardJumpDistance;
+  uint64_t propellerBackwardJumpDistance;
+  uint64_t propellerChainSplitThreshold;
+  std::vector<std::string> propellerDumpCfgs;
+  std::vector<std::string> propellerDebugSymbols;
+  std::vector<std::string> propellerOpts;
   llvm::StringRef printSymbolOrder;
   llvm::StringRef soName;
   llvm::StringRef sysroot;
   llvm::StringRef thinLTOCacheDir;
   llvm::StringRef thinLTOIndexOnlyArg;
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOObjectSuffixReplace;
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOPrefixReplace;
   std::string rpath;
struct Configuration {
   bool oFormatBinary;
   bool omagic;
   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 isStatic = false;
   bool sysvHash = false;
   bool target1Rel;

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 "InputFiles.h"
+#include "Propeller/PropellerConfig.h"
+#include "lld/Common/ErrorHandler.h"
+#include "lld/Common/Memory.h"
+#include "lld/Common/PropellerCommon.h"
+
+#include <algorithm>
+#include <vector>
+
+namespace lld {
+
+using elf::config;
+using elf::InputFile;
+using elf::objectFiles;
+
+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(BBOrder);
+  COPY_CONFIG(ChainSplitThreshold);
+  COPY_CONFIG(DebugSymbols);
+  COPY_CONFIG(ClusterMergeSizeThreshold);
+  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(SplitFuncs);
+  COPY_CONFIG(ReorderIP);
+#undef COPY_CONFIG
+}
+
+// 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>
+
+using llvm::StringRef;
+
+namespace lld {
+namespace propeller {
+
+struct PropellerConfig {
+  uint64_t optBackwardJumpDistance;
+  double optBackwardJumpWeight;
+  std::vector<StringRef> optBBOrder;
+  uint64_t optChainSplitThreshold;
+  std::vector<std::string> optDebugSymbols;
+  std::vector<std::string> optDumpCfgs;
+  uint64_t optClusterMergeSizeThreshold;
+  StringRef optDumpSymbolOrder;
+  double optFallthroughWeight;
+  uint64_t optForwardJumpDistance;
+  double optForwardJumpWeight;
+  bool optKeepNamedSymbols;
+  StringRef optLinkerOutputFile;
+  std::vector<std::string> optOpts;
+  bool optPrintStats;
+  StringRef optPropeller;
+  bool optReorderBlocks;
+  bool optReorderFuncs;
+  bool optSplitFuncs;
+  bool optReorderIP;
+};
+
+extern PropellerConfig propellerConfig;
+
+} // namespace propeller
+} // namespace lld
+
+#endif

lld/ELF/SyntheticSections.h

 
 #include "DWARF.h"
 #include "EhFrame.h"
 #include "InputSection.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/Endian.h"
 #include <functional>
+#include <map>
 
 namespace lld {
 namespace elf {
 class Defined;
 struct PhdrEntry;
 class SymbolTableBaseSection;
 class VersionNeedBaseSection;
 

 public:
   SymbolTableBaseSection(StringTableSection &strTabSec);
   void finalizeContents() override;
   size_t getSize() const override { return getNumSymbols() * entsize; }
   void addSymbol(Symbol *sym);
   unsigned getNumSymbols() const { return symbols.size() + 1; }
   size_t getSymbolIndex(Symbol *sym);
   ArrayRef<SymbolTableEntry> getSymbols() const { return symbols; }
+  // SymName end address -> <strtab_entry_offset, strtab_entry_size> mapping.
+  // See details in SymbolTableBaseSection::addSymbol.
+  std::map<uint64_t, std::pair<uint64_t, uint32_t>> EndsMap;
 
 protected:
   void sortSymTabSymbols();
 
   // A vector of symbols and their string table offsets.
   std::vector<SymbolTableEntry> symbols;
 
   StringTableSection &strTabSec;

lld/ELF/SyntheticSections.cpp

 #include "LinkerScript.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 #include "Writer.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
+#include "lld/Common/PropellerCommon.h"
 #include "lld/Common/Strings.h"
 #include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"
 #include "llvm/Object/ELFObjectFile.h"
for (const SymbolTableEntry &s : llvm::make_range(symbols.begin(), e))
     arr[s.sym->file].push_back(s);
 
   auto i = symbols.begin();
   for (std::pair<InputFile *, std::vector<SymbolTableEntry>> &p : arr)
     for (SymbolTableEntry &entry : p.second)
       *i++ = entry;
 }
 
+// When calling addSymbol, we add each BB symbol in the reverse order of its
+// index. For example, we add bb symbols in such a way:
+//     addSymbol("aaaa.BB.foo")
+//     addSymbol("aaa.BB.foo")
+//     addSymbol("aa.BB.foo")
+//     addSymbol("a.BB.foo")
+//
+// Note, the compiler makes sure the generated "aaaa.BB.foo", "aaa.BB.foo", etc
+// in the object strtab are stored optimally - that only "aaaa.BB.foo" is stored
+// in the strtab.
+// [Symtab section]
+//    [symbol name]  [strtab offset]
+//    aaaa.BB.foo    0
+//     aaa.BB.foo    1
+//      aa.BB.foo    2
+//       a.BB.foo    3
+// [Strtab section]
+//    aaaa.BB.foo\0\0
+//
+// "EndsMap" here stores the mapping from the end address of StringRef to a pair
+// of <strtab offset, size of the string>. For example:
+// From the object file we have the following StringRefs:
+//     aaaa.BB.foo   [start=400, size=11]
+//      aaa.BB.foo   [start=401, size=10]
+//       aa.BB.foo   [start=402, size=9]
+//        a.BB.foo   [start=403, size=8]
+// Note: the end address for all the 4 symbols are 411.
+// After adding "aaaa.BB.foo", we have the following StrTab and EndMap:
+//
+// Strtab:
+//     dummy\0
+//     aaaa.BB.foo\0     occupies [6-17]
+//     \0
+//
+// EndsMap:
+//   {
+//      411:{6,11}
+//   }
+// Then we try to add "aaa.BB.foo", which has the same "EndKey" 411, so we know
+// we can resue the strtab entry from 6-17, and don't create a new strtabe entry
+// we just reuse the existing one.
 void SymbolTableBaseSection::addSymbol(Symbol *b) {
   // Adding a local symbol to a .dynsym is a bug.
   assert(this->type != SHT_DYNSYM || !b->isLocal());
+  assert(this->type != SHT_DYNSYM || !b->isLocal());
+  StringRef SName = b->getName();
+  uint64_t EndKey = (uint64_t)(SName.data() + SName.size());
+  auto I = EndsMap.find(EndKey);
+  if (I != EndsMap.end()) {
+    uint64_t offset = I->second.first;
+    uint32_t size = I->second.second;
+    int64_t diff = size - SName.size();
+    if (diff >= 0) {
+      uint64_t new_offset = offset + diff;
+      symbols.push_back({b, new_offset});
+      return;
+    }
+  }
 
   bool hashIt = b->isLocal();
-  symbols.push_back({b, strTabSec.addString(b->getName(), hashIt)});
+  uint32_t offset = strTabSec.addString(b->getName(), hashIt);
+  symbols.push_back({b, offset});
+  if (lld::propeller::SymbolEntry::isBBSymbol(b->getName())) {
+    EndsMap.emplace(std::piecewise_construct, std::forward_as_tuple(EndKey),
+                    std::forward_as_tuple(offset, SName.size()));
+  }
 }
 
 size_t SymbolTableBaseSection::getSymbolIndex(Symbol *sym) {
   if (this == mainPart->dynSymTab)
     return sym->dynsymIndex;
 
   // Initializes symbol lookup tables lazily. This is used only for -r,
   // -emit-relocs and dynsyms in partitions other than the main one.

lld/ELF/Writer.cpp

 //===- Writer.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
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
 #include "AArch64ErrataFix.h"
 #include "ARMErrataFix.h"
 #include "CallGraphSort.h"
 #include "Config.h"
+#include "LinkerPropeller.h"
 #include "LinkerScript.h"
 #include "MapFile.h"
 #include "OutputSections.h"
 #include "Relocations.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Memory.h"
+#include "lld/Common/PropellerCommon.h"
 #include "lld/Common/Strings.h"
 #include "lld/Common/Threads.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/xxhash.h"
 #include <climits>
static bool shouldKeepInSymtab(const Defined &sym) {
   if (config->discard == DiscardPolicy::None)
     return true;
 
   // If -emit-reloc is given, all symbols including local ones need to be
   // copied because they may be referenced by relocations.
   if (config->emitRelocs)
     return true;
 
+  if (lld::propeller::isBBSymbolAndKeepIt(sym.getName()))
+    return true;
+
   // In ELF assembly .L symbols are normally discarded by the assembler.
   // If the assembler fails to do so, the linker discards them if
   // * --discard-locals is used.
   // * The symbol is in a SHF_MERGE section, which is normally the reason for
   //   the assembler keeping the .L symbol.
   StringRef name = sym.getName();
   bool isLocal = name.startswith(".L") || name.empty();
   if (!isLocal)

 
 // Local symbols are not in the linker's symbol table. This function scans
 // each object file's symbol table to copy local symbols to the output.
 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   if (!in.symTab)
     return;
   for (InputFile *file : objectFiles) {
     ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
+    std::vector<Symbol *> localNonBBSymbols;
+    std::vector<Symbol *> localBBSymbols;
     for (Symbol *b : f->getLocalSymbols()) {
       if (!b->isLocal())
         fatal(toString(f) +
               ": broken object: getLocalSymbols returns a non-local symbol");
       auto *dr = dyn_cast<Defined>(b);
 
       // No reason to keep local undefined symbol in symtab.
       if (!dr)
         continue;
       if (!includeInSymtab(*b))
         continue;
       if (!shouldKeepInSymtab(*dr))
         continue;
-      in.symTab->addSymbol(b);
+
+      if (lld::propeller::SymbolEntry::isBBSymbol(b->getName()))
+        localBBSymbols.emplace_back(b);
+      else
+        localNonBBSymbols.emplace_back(b);
     }
+
+    // We need to add bbsymbols in reverse order of their size. See details in
+    // SymbolTableBaseSection::addSymbol(Symbol *b).
+    llvm::sort(localBBSymbols, [](Symbol *A, Symbol *B) {
+      return A->getName().size() > B->getName().size();
+    });
+
+    // Add BB symbols to SymTab first.
+    for (auto *S : localBBSymbols)
+      in.symTab->addSymbol(S);
+
+    for (auto *S : localNonBBSymbols)
+      in.symTab->addSymbol(S);
   }
 }
 
 // Create a section symbol for each output section so that we can represent
 // relocations that point to the section. If we know that no relocation is
 // referring to a section (that happens if the section is a synthetic one), we
 // don't create a section symbol for that section.
 template <class ELFT> void Writer<ELFT>::addSectionSymbols() {

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 containsAddress(uint64_t A) const {
+    return Addr <= A && A < Addr + Size;
+  }
+
+  bool containsAnotherSymbol(SymbolEntry *O) const {
+    if (O->Size == 0) {
+      // Note if O's size is 0, we allow O on the end boundary. For example, if
+      // foo.BB.4 is at address 0x10. foo is [0x0, 0x10), we then assume foo
+      // contains foo.BB.4.
+      return this->Addr <= O->Addr && O->Addr <= this->Addr + this->Size;
+    }
+    return containsAddress(O->Addr) && containsAddress(O->Addr + O->Size - 1);
+  }
+
+  bool operator<(const SymbolEntry &Other) const {
+    return this->Ordinal < Other.Ordinal;
+  }
+
+  bool isFunction() const {
+    return this->Type == llvm::object::SymbolRef::ST_Function;
+  }
+
+  // Return true if this SymbolEntry is a containing function for BBName. For
+  // example, if BBName is given as "aa.BB.foo", and SymbolEntry.Name = "foo",
+  // then SymbolEntry.isFunctionForBBName(BBName) == true.  BBNames are from ELF
+  // object files.
+  bool isFunctionForBBName(StringRef BBName) const {
+    auto A = BBName.split(BASIC_BLOCK_SEPARATOR);
+    if (A.second == Name)
+      return true;
+    for (auto N : Aliases)
+      if (A.second == N)
+        return true;
+    return false;
+  }
+
+  // Return true if "SymName" is a BB symbol, e.g., in the form of
+  // "a.BB.funcname", and set FuncName to the part after ".BB.", BBIndex to
+  // before ".BB.", if the pointers are nonnull.
+  static bool isBBSymbol(const StringRef &SymName,
+                         StringRef *FuncName = nullptr,
+                         StringRef *BBIndex = nullptr) {
+    if (SymName.empty())
+      return false;
+    auto R = SymName.split(BASIC_BLOCK_SEPARATOR);
+    if (R.second.empty())
+      return false;
+    for (auto *I = R.first.bytes_begin(), *J = R.first.bytes_end(); I != J; ++I)
+      if (strchr(BASIC_BLOCK_UNIFIED_CHARACTERS, *I) == NULL)
+        return false;
+    if (FuncName)
+      *FuncName = R.second;
+    if (BBIndex)
+      *BBIndex = R.first;
+    return true;
+  }
+
+  static BBTagTypeEnum toBBTagType(const char c) {
+    switch (c) {
+    case 'a':
+      return BB_NORMAL;
+    case 'r':
+      return BB_RETURN;
+    case 'l':
+      return BB_LANDING_PAD;
+    case 'L':
+      return BB_RETURN_AND_LANDING_PAD;
+    default:;
+    }
+    return BB_NONE;
+  }
+
+  static const uint64_t INVALID_ADDRESS = uint64_t(-1);
+};
+
+struct SymbolEntryOrdinalLessComparator {
+  bool operator()(SymbolEntry *S1, SymbolEntry *S2) const {
+    if (!S1 && S2)
+      return true;
+    if ((S1 && !S2) || (!S1 && !S2))
+      return false;
+    return S1->Ordinal < S2->Ordinal;
+  }
+};
+
+} // namespace propeller
+} // namespace lld
+#endif