[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

324

Add a function comment for this.

334

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

341–343

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

358

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

277

lld/ code uses variableName. Please fix.

[MaskRay]

lld/ELF/CallGraphSort.cpp

8–9

This large comment is now stale.

277

static void

312

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

317

inline the used-once variable.

lld/ELF/Options.td

340

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

75

move after TargetParser for an alphabetical order.

lld/ELF/CallGraphSort.cpp

9–12

using LLVM call graph profile data ...

12

TLB misses and i-cache misses

277

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.

279

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

317

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

332

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

340

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.

341

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

278

Nit: delete this comment.

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

283

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

61–62

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
   TargetParser
+  TransformUtils
 
   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> applyCDSort();
+
 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:
-/// * Cluster
-///   * An ordered list of input sections which are laid out as a unit. At the
-///     beginning of the algorithm each input section has its own cluster and
-///     the weight of the cluster is the sum of the weight of all incoming
-///     edges.
-/// * Call-Chain Clustering (C³) Heuristic
-///   * Defines when and how clusters are combined. Pick the highest weighted
-///     input section then add it to its most likely predecessor if it wouldn't
-///     penalize it too much.
-/// * Density
-///   * The weight of the cluster divided by the size of the cluster. This is a
-///     proxy for the amount of execution time spent per byte of the cluster.
-///
-/// 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
+/// The file is responsible for sorting sections using LLVM call graph profile
+/// data by placing frequently executed code sections together. The goal of the
+/// placement is to improve the runtime performance of the final executable by
+/// arranging code sections so that i-TLB misses and i-cache misses are reduced.
 ///
+/// The algorithm first builds a call graph based on the profile data and then
+/// iteratively merges "chains" (ordered lists) of input sections which will be
+/// laid out as a unit. There are two implementations for deciding how to
+/// merge a pair of chains:
+///  - a simpler one, referred to as Call-Chain Clustering (C^3), that follows
+///    "Optimizing Function Placement for Large-Scale Data-Center Applications"
+/// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
+/// - a more advanced one, referred to as Cache-Directed-Sort (CDSort), which
+///   typically produces layouts with higher locality, and hence, yields fewer
+///   instruction cache misses on large binaries.
 //===----------------------------------------------------------------------===//
 
 #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 {
struct Cluster {
   int next;
   int prev;
   uint64_t size;
   uint64_t weight = 0;
   uint64_t initialWeight = 0;
   Edge bestPred = {-1, 0};
 };
 
+/// Implementation of the Call-Chain Clustering (C^3). The goal of this
+/// algorithm is to improve runtime performance of the executable by arranging
+/// code sections such that page table and i-cache misses are minimized.
+///
+/// Definitions:
+/// * Cluster
+///   * An ordered list of input sections which are laid out as a unit. At the
+///     beginning of the algorithm each input section has its own cluster and
+///     the weight of the cluster is the sum of the weight of all incoming
+///     edges.
+/// * Call-Chain Clustering (C³) Heuristic
+///   * Defines when and how clusters are combined. Pick the highest weighted
+///     input section then add it to its most likely predecessor if it wouldn't
+///     penalize it too much.
+/// * Density
+///   * The weight of the cluster divided by the size of the cluster. This is a
+///     proxy for the amount of execution time spent per byte of the cluster.
+///
+/// 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
 class CallGraphSort {
 public:
   CallGraphSort();
 
   DenseMap<const InputSectionBase *, int> run();
 
 private:
   std::vector<Cluster> clusters;
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.
+static 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) {
+      // inSec does not appear before in the graph.
+      sections.push_back(inSec);
+      assert(inSec->getSize() > 0 && "found a function with 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;
+
+    callCounts.push_back(std::make_pair(std::make_pair(from, to), weight));
+    // Assume that the jump is at the middle of the input section. The profile
+    // data does not contain jump offsets.
+    callOffsets.push_back((funcSizes[from] + 1) / 2);
+    funcCounts[to] += weight;
+  }
+}
+
+// Sort sections by the profile data using the Cache-Directed Sort algorithm.
+// The placement is done by optimizing the locality by co-locating frequently
+// executed code sections together.
+DenseMap<const InputSectionBase *, int> elf::applyCDSort() {
+  // 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.
+  std::vector<uint64_t> sortedSections =
+      applyCDSLayout(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 Cache-Directed-Sort ordering algorithm.
 DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
+  if (config->useCacheDirectedSort)
+    return applyCDSort();
   return CallGraphSort().run();
 }

lld/ELF/Config.h

 };
 
 // For -Bno-symbolic, -Bsymbolic-non-weak-functions, -Bsymbolic-functions,
 // -Bsymbolic-non-weak, -Bsymbolic.
 enum class BsymbolicKind { None, NonWeakFunctions, Functions, NonWeak, 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 useCacheDirectedSort;
   bool warnBackrefs;
   llvm::SmallVector<llvm::GlobPattern, 0> warnBackrefsExclude;
   bool warnCommon;
   bool warnMissingEntry;
   bool warnSymbolOrdering;
   bool writeAddends;
   bool zCombreloc;
   bool zCopyreloc;

lld/ELF/Driver.cpp

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->useCacheDirectedSort = args.hasFlag(
+      OPT_use_cache_directed_sort, OPT_no_use_cache_directed_sort, 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_cache_directed_sort: BB<"use-cache-directed-sort",
+    "Reorder input sections with cache-directed sort",
+    "Do not use cache-directed sort to reorder input sections">;
+
 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",

lld/test/ELF/cgprofile-txt.s

 # RUN: echo "TooManyPreds3 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds4 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds5 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds6 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds7 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds8 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds9 TooManyPreds 10" >> %t.call_graph
 # RUN: echo "TooManyPreds10 TooManyPreds 11" >> %t.call_graph
-# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph -o %t2
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph --no-use-cache-directed-sort -o %t2
 # RUN: llvm-readobj --symbols %t2 | FileCheck %s
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph --use-cache-directed-sort -o %t2
+# RUN: llvm-readobj --symbols %t2 | FileCheck %s --check-prefix=CDSORT
 
     .section    .text.D,"ax",@progbits
 D:
     retq
 
     .section    .text.C,"ax",@progbits
     .globl  C
 C:

 # CHECK-NEXT:     Value: 0x20113E
 # CHECK:          Name: GB
 # CHECK-NEXT:     Value: 0x20113F
 # CHECK:          Name: _init
 # CHECK-NEXT:     Value: 0x201140
 # CHECK:          Name: _init2
 # CHECK-NEXT:     Value: 0x201141
 
+# CDSORT:          Name: D
+# CDSORT-NEXT:     Value: 0x201123
+# CDSORT:          Name: TooManyPreds
+# CDSORT-NEXT:     Value: 0x20112F
+# CDSORT:          Name: TooManyPreds10
+# CDSORT-NEXT:     Value: 0x20112E
+# CDSORT:          Name: C
+# CDSORT-NEXT:     Value: 0x201122
+# CDSORT:          Name: B
+# CDSORT-NEXT:     Value: 0x201121
+# CDSORT:          Name: A
+# CDSORT-NEXT:     Value: 0x201120
+# CDSORT:          Name: TS
+# CDSORT-NEXT:     Value: 0x20113D
+# CDSORT:          Name: PP
+# CDSORT-NEXT:     Value: 0x20113C
+# CDSORT:          Name: QC
+# CDSORT-NEXT:     Value: 0x20113E
+# CDSORT:          Name: GB
+# CDSORT-NEXT:     Value: 0x20113F
+# CDSORT:          Name: _init
+# CDSORT-NEXT:     Value: 0x201140
+# CDSORT:          Name: _init2
+# CDSORT-NEXT:     Value: 0x201141
+
 # NOSORT:          Name: D
 # NOSORT-NEXT:     Value: 0x201120
 # NOSORT:          Name: TooManyPreds
 # NOSORT-NEXT:     Value: 0x201124
 # NOSORT:          Name: TooManyPreds10
 # NOSORT-NEXT:     Value: 0x201138
 # NOSORT:          Name: C
 # NOSORT-NEXT:     Value: 0x201121

lld/test/ELF/cgprofile-txt2.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo "A B 5" > %t.call_graph
 # RUN: echo "B C 50" >> %t.call_graph
 # RUN: echo "C D 40" >> %t.call_graph
 # RUN: echo "D B 10" >> %t.call_graph
-# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph -o %t2
-# RUN: llvm-readobj --symbols %t2 | FileCheck %s
-
-# CHECK:      Name: A
-# CHECK-NEXT: Value: 0x201123
-# CHECK:      Name: B
-# CHECK-NEXT: Value: 0x201120
-# CHECK:      Name: C
-# CHECK-NEXT: Value: 0x201121
-# CHECK:      Name: D
-# CHECK-NEXT: Value: 0x201122
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph --no-use-cache-directed-sort -o %t2
+# RUN: llvm-readobj --symbols %t2 | FileCheck %s --check-prefix=CHECKC3
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph --use-cache-directed-sort -o %t2
+# RUN: llvm-readobj --symbols %t2 | FileCheck %s --check-prefix=CHECKCDS
+
+# CHECKC3:      Name: A
+# CHECKC3-NEXT: Value: 0x201123
+# CHECKC3:      Name: B
+# CHECKC3-NEXT: Value: 0x201120
+# CHECKC3:      Name: C
+# CHECKC3-NEXT: Value: 0x201121
+# CHECKC3:      Name: D
+# CHECKC3-NEXT: Value: 0x201122
+
+# CHECKCDS:      Name: A
+# CHECKCDS-NEXT: Value: 0x201120
+# CHECKCDS:      Name: B
+# CHECKCDS-NEXT: Value: 0x201121
+# CHECKCDS:      Name: C
+# CHECKCDS-NEXT: Value: 0x201122
+# CHECKCDS:      Name: D
+# CHECKCDS-NEXT: Value: 0x201123
 
 .section    .text.A,"ax",@progbits
 .globl  A
 A:
  nop
 
 .section    .text.B,"ax",@progbits
 .globl  B