[ELF] A new code layout algorithm for function reordering [3a/3]

[spupyrev]

Summary

We are brining a new algorithm for function layout (reordering) based on the
call graph (extracted from a profile data). The algorithm is an improvement of
top of a known heuristic, C^3. It tries to co-locate hot and frequently executed
together functions in the resulting ordering. Unlike C^3, it explores a larger
search space and have an objective closely tied to the performance of
instruction and i-TLB caches. Hence, the name CDS = Cache-Directed Sort.
The algorithm can be used at the linking or post-linking (e.g., BOLT) stage.
Refer to https://reviews.llvm.org/D152834 for the actual implementation of the
reordering algorithm.

This diff adds a linker option to replace the existing C^3 heuristic with CDS.
The new behavior can be turned on by passing "--use-cache-directed-sort".
(the plan is to make it default in a next diff)

Perf-impact
clang-10 binary (built with LTO+AutoFDO/CSSPGO): wins on top of C^3 in [0.3%..0.8%]
rocksDB-8 binary (built with LTO+CSSPGO): wins on top of C^3 in [0.8%..1.5%]

Note that function layout affects the perf the most on older machines (with
smaller instruction/iTLB caches) and when huge pages are not enabled. The impact
on newer processors with huge pages enabled is likely neutral/minor.

[spupyrev]

upd

[rahmanl]

lld/ELF/CallGraphSort.cpp

314

Add a function comment for this.

324

It doesn't look like this can take configurations by flags?

331–333

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

345

https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

lld/ELF/CallGraphSort.h

17

Why are we abbreviating here? It's not clear to me what CDS stands for.

[spupyrev]

addressing comments, adding a test for cdsort

[MaskRay]

Thank you for contributing a new algorithm and sorry for not commenting earlier.

A new code layout algorithm for function reordering [3a/3]

lld/ELF patches are usually tagged [ELF] . You should be able to find many examples with git log -- lld/ELF. [3a/3] seems unclear.
I think it's much better to mention https://reviews.llvm.org/D152834 in the summary as [3a/3] isn't clear whether 1/3 and 2/3 are :)

I'd like to know a plan whether we are going to remove the existing hfsort heuristic, and state this in the summary.
In D152834 you mentioned it, but many folks reading lld including me do not follow bolt.

--use-cdsort is the default and overrides the existing hfsort. This should be stated as well.

I will need some time to read D152834.

lld/ELF/CallGraphSort.cpp

267

lld/ code uses variableName. Please fix.

[MaskRay]

lld/ELF/CallGraphSort.cpp

9

This large comment is now stale.

267

static void

302

We don't add a blank line after variable declarations.

307

inline the used-once variable.

lld/ELF/Options.td

323

New options use BB.

[spupyrev]

Thanks for looking into this. I made the requested changes

[spupyrev]

rebasing to latest

[MaskRay]

Thanks for the update.

https://maskray.me/blog/2021-08-08-toolchain-testing#the-test-checks-at-the-wrong-layer We need some unittests in llvm/. I created D159527

lld/ELF/CMakeLists.txt

74

move after TargetParser for an alphabetical order.

lld/ELF/CallGraphSort.cpp

39

using LLVM call graph profile data ...

42

TLB misses and i-cache misses

267

lld code prefers SmallVector<X, 0> for a smaller size and usually better performance.

D159526 will change these to use ArrayRef, enabling SmallVector<X, 0> at call sites.

269

the nested pair feels unnatural to me. I updated D159526 to change the element type to a std::tuple

307

This needs a comment: // Assume that the jump is at the middle of the input section. The profile data does not contain jump offsets.

322

buildCallGraph is called once and the conventional style just remove the extra function.

lld/ELF/CallGraphSort.h

17

This does not need to be a public API. Apply seems less appropriate in the context. I created D159526 to rename this to compute*

lld/ELF/Options.td

323

I feel that this abbreviated option name isn't intuitive.

A similar --call-graph-profile-sort intentionally picks a long but descriptive name. I think --use-cache-directed-sort will be better.

I suggest we make --no-use-cache-directed-sort the default and then change the default in another patch.

324

Reorder input sections with cache-directed sort.

[spupyrev]

comments

[spupyrev]

renaming the option

[MaskRay]

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

[spupyrev]

In D152840#4648482, @MaskRay wrote:

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

I have an impression the changes are made in the follow-up D159526 (which I'd prefer to land after this one). Do I miss something?

[MaskRay]

In D152840#4648483, @spupyrev wrote:

In D152840#4648482, @MaskRay wrote:

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

I have an impression the changes are made in the follow-up D159526 (which I'd prefer to land after this one). Do I miss something?

You are right. You may rebase this patch on top of D159526 :)

[spupyrev]

In D152840#4648582, @MaskRay wrote:

In D152840#4648483, @spupyrev wrote:

In D152840#4648482, @MaskRay wrote:

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

I have an impression the changes are made in the follow-up D159526 (which I'd prefer to land after this one). Do I miss something?

You are right. You may rebase this patch on top of D159526 :)

I suggest to rebase D159526 on top of this one

[MaskRay]

In D152840#4648633, @spupyrev wrote:

In D152840#4648582, @MaskRay wrote:

In D152840#4648483, @spupyrev wrote:

In D152840#4648482, @MaskRay wrote:

Thanks for the update. I am mainly waiting for the renamed function (applyCDSort does not convey the meaning well), changes of nested std::pair and std::vector => SmallVector<*, 0>

I have an impression the changes are made in the follow-up D159526 (which I'd prefer to land after this one). Do I miss something?

You are right. You may rebase this patch on top of D159526 :)

I suggest to rebase D159526 on top of this one

D159526 performed the rename. If this patch is applied, applyCDSort in lld/ELF will need to be updated again. This is exactly the scenario I want to avoid.
D159527 added a unittest, which I consider necessary for making more application of the new layout algorithm.
(lld/test/ELF is not supposed to test functional change in llvm/ https://maskray.me/blog/2021-08-08-toolchain-testing#the-test-checks-at-the-wrong-layer)

[spupyrev]

D159526 performed the rename. If this patch is applied, applyCDSort in lld/ELF will need to be updated again. This is exactly the scenario I want to avoid.

Can you explain why renaming a function might be a problem and we may want to avoid this either in the linker or in the compiler?

I am not fully convinced that the newly proposed naming is preferred over the existing one. The new algorithm is called "cdsort" (which mimics the existing and commonly accepted name of "hfsort"), and it makes a sense to call the corresponding function "applyCDSort" as in "applyAlgorithmX". In contrast, "computeXXXlayout" might feel confusing, since the word "layout" often means a process.

[MaskRay]

In D152840#4649238, @spupyrev wrote:

D159526 performed the rename. If this patch is applied, applyCDSort in lld/ELF will need to be updated again. This is exactly the scenario I want to avoid.

Can you explain why renaming a function might be a problem and we may want to avoid this either in the linker or in the compiler?

I am not fully convinced that the newly proposed naming is preferred over the existing one. The new algorithm is called "cdsort" (which mimics the existing and commonly accepted name of "hfsort"), and it makes a sense to call the corresponding function "applyCDSort" as in "applyAlgorithmX". In contrast, "computeXXXlayout" might feel confusing, since the word "layout" often means a process.

I think apply* is often used when some structs are changed, e.g. applyDomTreeUpdates.
If we have a section order, then we use that to change the list of sections, we can say apply....
If we just compute the section order, apply* is not appropriate.
compute* is the conventional name here.

[MaskRay]

I have also explained that SmallVector<*, 0> is preferred in lld/ELF code, so I have a vector => ArrayRef refactoring.
We should also get rid of buildCallGraph, which uses a number of output parameters, while the function can just be inlined into apply* (to be renamed).

[MaskRay]

Instead of having a --use-*, the best is probably to create a JJ<"call-graph-profile-sort=", ...> (values: hfsort,cdsort),
make the existing --call-graph-profile-sort an alias (FF<"call-graph-profile-sort", ...>, Alias<call_graph_profile_sort>, AliasArgs<"hfsort">),
then add a BB for --no-call-graph-profile-sort.

(I'll be out of town during 9-29 ~ 10-9)

[MaskRay]

In D152840#4650105, @MaskRay wrote:

Instead of having a --use-*, the best is probably to create a JJ<"call-graph-profile-sort=", ...> (values: hfsort,cdsort),
make the existing --call-graph-profile-sort an alias (FF<"call-graph-profile-sort", ...>, Alias<call_graph_profile_sort>, AliasArgs<"hfsort">),
then add a BB for --no-call-graph-profile-sort.

(I'll be out of town during 9-29 ~ 10-9)

See D159544

[spupyrev]

minor

[spupyrev]

tests

[spupyrev]

nit

[MaskRay]

Thanks for the update.

lld/ELF/CallGraphSort.cpp

268

Nit: delete this comment.

"// Create the graph." below is clear enough.

273

sections can use SmallVector as well.

We can use one type for multiple variables

SmallVector<uint64_t, 0> funcSizes, funcCounts, callOffsets;`

lld/ELF/Config.h

59–60

update this comment

[spupyrev]

nits

[MaskRay]

lld/docs/ld.lld.1 needs an update as well. The format is difficult to write... you can use man lld/docs/ld.lld.1 to check whether it looks right.

[spupyrev]

edited ld.lld.1

[MaskRay]

LGTM! Thanks for bearing with me about all the nits.

I'd like to have tests at the proper layer. Does D159527 look good to you?

lld/ELF/CMakeLists.txt

add_lld_library(lldELF
   DebugInfoDWARF
   Demangle
   LTO
   MC
   Object
   Option
   Passes
   Support
+  TransformUtils
   TargetParser
 
   LINK_LIBS
   lldCommon
   ${imported_libs}
   ${LLVM_PTHREAD_LIB}
 
   DEPENDS
   ELFOptionsTableGen
   intrinsics_gen
   )

lld/ELF/CallGraphSort.h

 //===- CallGraphSort.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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_CALL_GRAPH_SORT_H
 #define LLD_ELF_CALL_GRAPH_SORT_H
 
 #include "llvm/ADT/DenseMap.h"
 
 namespace lld::elf {
 class InputSectionBase;
 
+llvm::DenseMap<const InputSectionBase *, int> applyCDS();
+
 llvm::DenseMap<const InputSectionBase *, int> computeCallGraphProfileOrder();
 } // namespace lld::elf
 
 #endif

lld/ELF/CallGraphSort.cpp

 //===- CallGraphSort.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
 //
 //===----------------------------------------------------------------------===//
 ///
 /// Implementation of Call-Chain Clustering from: Optimizing Function Placement
 /// for Large-Scale Data-Center Applications
 /// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
 ///
 /// The goal of this algorithm is to improve runtime performance of the final
 /// executable by arranging code sections such that page table and i-cache
 /// misses are minimized.
 ///
 /// Definitions:

 /// It does so given a call graph profile by the following:
 /// * Build a weighted call graph from the call graph profile
 /// * Sort input sections by weight
 /// * For each input section starting with the highest weight
 ///   * Find its most likely predecessor cluster
 ///   * Check if the combined cluster would be too large, or would have too low
 ///     a density.
 ///   * If not, then combine the clusters.
 /// * Sort non-empty clusters by density
 ///
 //===----------------------------------------------------------------------===//
 
 #include "CallGraphSort.h"
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "Symbols.h"
 #include "llvm/Support/FileSystem.h"
+#include "llvm/Transforms/Utils/CodeLayout.h"
 
 #include <numeric>
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::elf;
 
 namespace {
for (int leader : sorted)
         if (i == leader)
           break;
       }
   }
 
   return orderMap;
 }
 
+using CallT = std::pair<uint64_t, uint64_t>;
+
+// Fill in necessary data for Cache-Directed Sort.
+void buildCallGraph(std::vector<uint64_t> &FuncSizes,
+                    std::vector<uint64_t> &FuncCounts,
+                    std::vector<std::pair<CallT, uint64_t>> &CallCounts,
+                    std::vector<uint64_t> &CallOffsets,
+                    std::vector<const InputSectionBase *> &Sections) {
+  MapVector<SectionPair, uint64_t> &Profile = config->callGraphProfile;
+  DenseMap<const InputSectionBase *, size_t> SecToTargetId;
+
+  auto getOrCreateNode = [&](const InputSectionBase *InSec) -> size_t {
+    auto Res = SecToTargetId.try_emplace(InSec, Sections.size());
+    if (Res.second) {
+      // Isec does not appear before in the graph.
+      Sections.push_back(InSec);
+      assert(InSec->getSize() > 0 && "found a function of zero size");
+      FuncSizes.push_back(InSec->getSize());
+      FuncCounts.push_back(0);
+    }
+    return Res.first->second;
+  };
+
+  // Create the graph
+  for (std::pair<SectionPair, uint64_t> &C : Profile) {
+    const InputSectionBase *FromSB = cast<InputSectionBase>(C.first.first);
+    const InputSectionBase *ToSB = cast<InputSectionBase>(C.first.second);
+    // Ignore edges between input sections belonging to different sections.
+    if (FromSB->getOutputSection() != ToSB->getOutputSection())
+      continue;
+
+    uint64_t Weight = C.second;
+    // Ignore edges with zero weight.
+    if (Weight == 0)
+      continue;
+
+    size_t From = getOrCreateNode(FromSB);
+    size_t To = getOrCreateNode(ToSB);
+
+    // Ignore self-edges (recursive calls).
+    if (From == To)
+      continue;
+
+    auto It = std::make_pair(From, To);
+    CallCounts.push_back(std::make_pair(It, Weight));
+    CallOffsets.push_back((FuncSizes[From] + 1) / 2);
+    FuncCounts[To] += Weight;
+  }
+}
+
+DenseMap<const InputSectionBase *, int> elf::applyCDS() {
+  // Creating a call graph and necessary data.
+  std::vector<uint64_t> FuncSizes;
+  std::vector<uint64_t> FuncCounts;
+  std::vector<std::pair<CallT, uint64_t>> CallCounts;
+  std::vector<uint64_t> CallOffsets;
+  std::vector<const InputSectionBase *> Sections;
+  buildCallGraph(FuncSizes, FuncCounts, CallCounts, CallOffsets, Sections);
+
+  // Run the layout algorithm.
+  CDSortConfig Config;
+  std::vector<uint64_t> SortedSections =
+      applyCDSLayout(Config, FuncSizes, FuncCounts, CallCounts, CallOffsets);
+
+  // Create the final order.
+  DenseMap<const InputSectionBase *, int> OrderMap;
+  int CurOrder = 1;
+  for (uint64_t SecIdx : SortedSections) {
+    OrderMap[Sections[SecIdx]] = CurOrder++;
+  }
+
+  return OrderMap;
+}
+
 // Sort sections by the profile data provided by --callgraph-profile-file.
 //
 // This first builds a call graph based on the profile data then merges sections
-// according to the C³ heuristic. All clusters are then sorted by a density
-// metric to further improve locality.
+// according either to the C³ or CDS algorithm.
 DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
+  if (config->useCDS)
+    return applyCDS();
+  else
     return CallGraphSort().run();
 }

lld/ELF/Config.h

 };
 
 // For -Bno-symbolic, -Bsymbolic-non-weak-functions, -Bsymbolic-functions,
 // -Bsymbolic.
 enum class BsymbolicKind { None, NonWeakFunctions, Functions, All };
 
 // For --build-id.
 enum class BuildIdKind { None, Fast, Md5, Sha1, Hexstring, Uuid };
 
 // For --discard-{all,locals,none}.
 enum class DiscardPolicy { Default, All, Locals, None };
 
 // For --icf={none,safe,all}.
 enum class ICFLevel { None, Safe, All };
 
 // For --strip-{all,debug}.
 enum class StripPolicy { None, All, Debug };
 
struct Config {
   bool thinLTOEmitIndexFiles;
   bool thinLTOIndexOnly;
   bool timeTraceEnabled;
   bool tocOptimize;
   bool pcRelOptimize;
   bool undefinedVersion;
   bool unique;
   bool useAndroidRelrTags = false;
+  bool useCDS = false;
   bool warnBackrefs;
   llvm::SmallVector<llvm::GlobPattern, 0> warnBackrefsExclude;
   bool warnCommon;
   bool warnMissingEntry;
   bool warnSymbolOrdering;
   bool writeAddends;
   bool zCombreloc;
   bool zCopyreloc;

lld/ELF/Driver.cpp

static void checkOptions() {
   if (config->fixCortexA53Errata843419 && config->emachine != EM_AARCH64)
     error("--fix-cortex-a53-843419 is only supported on AArch64 targets");
 
   if (config->fixCortexA8 && config->emachine != EM_ARM)
     error("--fix-cortex-a8 is only supported on ARM targets");
 
   if (config->fixCortexA8 && !config->isLE)
     error("--fix-cortex-a8 is not supported on big endian targets");
-  
   if (config->tocOptimize && config->emachine != EM_PPC64)
     error("--toc-optimize is only supported on PowerPC64 targets");
 
   if (config->pcRelOptimize && config->emachine != EM_PPC64)
     error("--pcrel-optimize is only supported on PowerPC64 targets");
 
   if (config->relaxGP && config->emachine != EM_RISCV)
     error("--relax-gp is only supported on RISC-V targets");
config->timeTraceGranularity =
       args::getInteger(args, OPT_time_trace_granularity, 500);
   config->trace = args.hasArg(OPT_trace);
   config->undefined = args::getStrings(args, OPT_undefined);
   config->undefinedVersion =
       args.hasFlag(OPT_undefined_version, OPT_no_undefined_version, false);
   config->unique = args.hasArg(OPT_unique);
   config->useAndroidRelrTags = args.hasFlag(
       OPT_use_android_relr_tags, OPT_no_use_android_relr_tags, false);
+  config->useCDS = args.hasFlag(OPT_use_cds, OPT_no_use_cds, false);
   config->warnBackrefs =
       args.hasFlag(OPT_warn_backrefs, OPT_no_warn_backrefs, false);
   config->warnCommon = args.hasFlag(OPT_warn_common, OPT_no_warn_common, false);
   config->warnSymbolOrdering =
       args.hasFlag(OPT_warn_symbol_ordering, OPT_no_warn_symbol_ordering, true);
   config->whyExtract = args.getLastArgValue(OPT_why_extract);
   config->zCombreloc = getZFlag(args, "combreloc", "nocombreloc", true);
   config->zCopyreloc = getZFlag(args, "copyreloc", "nocopyreloc", true);

lld/ELF/Options.td

 defm pack_dyn_relocs:
   EEq<"pack-dyn-relocs", "Pack dynamic relocations in the given format">,
   MetaVarName<"[none,android,relr,android+relr]">;
 
 defm use_android_relr_tags: BB<"use-android-relr-tags",
     "Use SHT_ANDROID_RELR / DT_ANDROID_RELR* tags instead of SHT_RELR / DT_RELR*",
     "Use SHT_RELR / DT_RELR* tags (default)">;
 
+defm use_cds: B<"use-cds",
+    "Use CDS to reorder functions in the binary",
+    "Do not use CDS to reorder functions in the binary">;
+
 def pic_veneer: F<"pic-veneer">,
   HelpText<"Always generate position independent thunks (veneers)">;
 
 defm pie: B<"pie",
     "Create a position independent executable",
     "Do not create a position independent executable (default)">;
 
 defm print_gc_sections: B<"print-gc-sections",