[llvm][Instrumentation] Add Call Graph Profile pass

[Bigcheese]

Summary

This patch adds support for generating a call graph profile from Branch Frequency Info.

Generating the CG Profile

The CGProfile module pass simply gets the block profile count for each BB and scans for call instructions. For each call instruction it adds an edge from the current function to the called function with the current BB block profile count as the weight.

After scanning all the functions, it generates an appending module flag containing the data. The format looks like:

!llvm.module.flags = !{!0} 
 
!0 = !{i32 5, !"CG Profile", !1} 
!1 = !{!2, !3, !4} ; List of edges
!2 = !{void ()* @a, void ()* @b, i64 32} ; Edge from a to b with a weight of 32
!3 = !{void (i1)* @freq, void ()* @a, i64 11} 
!4 = !{void (i1)* @freq, void ()* @b, i64 20}

[MaskRay]

BTW, can you take a look at https://reviews.llvm.org/D46228 ?

[compnerd]

lib/Transforms/Instrumentation/CGProfile.cpp

48 ↗

(On Diff #151059)

Can this not be const auto &F : M?

53 ↗

(On Diff #151059)

Can this not be const auto &BB : F?

57 ↗

(On Diff #151059)

Can this not be const auto &I : BB?

[Bigcheese]

Address review comments by adding const where applicable.

lib/Transforms/Instrumentation/CGProfile.cpp

48 ↗

(On Diff #151059)

No, because of getAnalysis.

[compnerd]

I assume that there is/will be a different change to the frontend to enable this for users?

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

146 ↗

(On Diff #151215)

Probably would be nice to hoist the Streamer.getContext() out of the loop.

auto &C = Streamer.getContext();

lib/Transforms/Instrumentation/CGProfile.cpp

75–88 ↗

(On Diff #151215)

Would be nice to move this (L75-88) into a helper function (UpdateModuleMetadata?)

[Bigcheese]

Address review comments.

Change to using ValueAsMetadata instead of strings and add a check to the verifier.

[Bigcheese]

This is enabled by default as the time and size overhead is so small.

[Bigcheese]

Use the correct diff.

[compnerd]

Thanks for the changes!

[davidxl]

This patch totally fell out of my radar. I will take a closer look at it.

[davidxl]

I am with Chandler here. Adding this pass to the legacy PM only will slow down the eventual migration to the new PM. It is better to do the new PM or both.

llvm/trunk/lib/Transforms/Instrumentation/CGProfile.cpp

52 ↗

(On Diff #152406)

You can check the existence of function entry count to decide whether to skip function earlier.

61 ↗

(On Diff #152406)

Use CallSite interface instead so that InvokeInst is handled as well:

CallSite CS(&I);
 if (!CS) continue;

Chandler has plan to unify the CallInst and InvokeInst in the future, but for now, CallSIte is the way to go.

65 ↗

(On Diff #152406)

you may want to check TTI to see if isLoweredToCall returns true.

68 ↗

(On Diff #152406)

You may also check indirect callsite to see if it has value profile data (indirect call target). If it has, you can create edges to the targets as well.

(I assume this information is for function layout purpose by the linker).

[chandlerc]

I had to revert this because the embedded function analysis runner inside the legacy pass manager for module passes appears to leak. =/ At least we found LeakSanitizer reports on the bots because of this commit.

Up to you whether you want to try and fix LegacyPM here or just switch to working on this w/ the new PM.

[Bigcheese]

• Move to new PM
• Use CallSite
• Bail early if no profile counts
• Use TargetTransformInfo::isLoweredToCall

llvm/trunk/lib/Transforms/Instrumentation/CGProfile.cpp

68 ↗

(On Diff #152406)

Is there an example where this is used? I'm not familiar with value profile data.

[davidxl]

The interface to get indirect call target value profile is bool getValueProfDataFromInst. See how it is used in ICallPromotionAnalysis::getPromotionCandidatesForInstruction(..) method.

[Bigcheese]

Add support for indirect calls using value profiling data.

[davidxl]

lib/Transforms/Instrumentation/CGProfile.cpp

66 ↗

(On Diff #152983)

The lowering check and count update code is shared between indirect and direct calls, so perhaps add a helper lambda function for it?

[Bigcheese]

Remove duplication on updating Counts.

[davidxl]

LGTM.

ELF/CMakeLists.txt

add_lld_library(lldELF
   Arch/AVR.cpp
   Arch/Mips.cpp
   Arch/MipsArchTree.cpp
   Arch/PPC.cpp
   Arch/PPC64.cpp
   Arch/SPARCV9.cpp
   Arch/X86.cpp
   Arch/X86_64.cpp
+  CallGraphSort.cpp
   Driver.cpp
   DriverUtils.cpp
   EhFrame.cpp
   Filesystem.cpp
   GdbIndex.cpp
   ICF.cpp
   InputFiles.cpp
   InputSection.cpp

ELF/CallGraphSort.h

+//===- CallGraphSort.h ------------------------------------------*- C++ -*-===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_CALL_GRAPH_SORT_H
+#define LLD_ELF_CALL_GRAPH_SORT_H
+
+#include "llvm/ADT/DenseMap.h"
+
+namespace lld {
+namespace elf {
+class InputSectionBase;
+
+llvm::DenseMap<const InputSectionBase *, int> computeCallGraphProfileOrder();
+} // namespace elf
+} // namespace lld
+
+#endif

ELF/CallGraphSort.cpp

+//===- CallGraphSort.cpp --------------------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// 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 layed 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 incomming
+///     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 ammount 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
+///
+//===----------------------------------------------------------------------===//
+
+#include "CallGraphSort.h"
+#include "OutputSections.h"
+#include "SymbolTable.h"
+#include "Symbols.h"
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::elf;
+
+namespace {
+struct Edge {
+  int From;
+  uint64_t Weight;
+};
+
+struct Cluster {
+  Cluster(int Sec, size_t S) {
+    Sections.push_back(Sec);
+    Size = S;
+  }
+
+  double getDensity() const {
+    if (Size == 0)
+      return 0;
+    return double(Weight) / double(Size);
+  }
+
+  std::vector<int> Sections;
+  size_t Size = 0;
+  uint64_t Weight = 0;
+  uint64_t InitialWeight = 0;
+  std::vector<Edge> Preds;
+};
+
+class CallGraphSort {
+public:
+  CallGraphSort();
+
+  DenseMap<const InputSectionBase *, int> run();
+
+private:
+  std::vector<Cluster> Clusters;
+  std::vector<const InputSectionBase *> Sections;
+
+  void groupClusters();
+};
+
+// Maximum ammount the combined cluster density can be worse than the original
+// cluster to consider merging.
+constexpr int MAX_DENSITY_DEGRADATION = 8;
+
+// Maximum cluster size in bytes.
+constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
+} // end anonymous namespace
+
+// Take the edge list in Config->CallGraphProfile, resolve symbol names to
+// Symbols, and generate a graph between InputSections with the provided
+// weights.
+CallGraphSort::CallGraphSort() {
+  llvm::MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
+                  uint64_t> &Profile = Config->CallGraphProfile;
+  DenseMap<const InputSectionBase *, int> SecToCluster;
+
+  auto GetOrCreateNode = [&](const InputSectionBase *IS) -> int {
+    auto Res = SecToCluster.insert(std::make_pair(IS, Clusters.size()));
+    if (Res.second) {
+      Sections.push_back(IS);
+      Clusters.emplace_back(Clusters.size(), IS->getSize());
+    }
+    return Res.first->second;
+  };
+
+  // Create the graph.
+  for (const auto &C : Profile) {
+    const auto *FromSB = cast<InputSectionBase>(C.first.first->Repl);
+    const auto *ToSB = cast<InputSectionBase>(C.first.second->Repl);
+    uint64_t Weight = C.second;
+
+    // Ignore edges between input sections belonging to different output
+    // sections.  This is done because otherwise we would end up with clusters
+    // containing input sections that can't actually be placed adjacently in the
+    // output.  This messes with the cluster size and density calculations.  We
+    // would also end up moving input sections in other output sections without
+    // moving them closer to what calls them.
+    if (FromSB->getOutputSection() != ToSB->getOutputSection())
+      continue;
+
+    int From = GetOrCreateNode(FromSB);
+    int To = GetOrCreateNode(ToSB);
+
+    Clusters[To].Weight += Weight;
+
+    if (From == To)
+      continue;
+
+    // Add an edge
+    Clusters[To].Preds.push_back({From, Weight});
+  }
+  for (Cluster &C : Clusters)
+    C.InitialWeight = C.Weight;
+}
+
+// It's bad to merge clusters which would degrade the density too much.
+static bool isNewDensityBad(Cluster &A, Cluster &B) {
+  double NewDensity = double(A.Weight + B.Weight) / double(A.Size + B.Size);
+  if (NewDensity < A.getDensity() / MAX_DENSITY_DEGRADATION)
+    return true;
+  return false;
+}
+
+static void mergeClusters(Cluster &Into, Cluster &From) {
+  Into.Sections.insert(Into.Sections.end(), From.Sections.begin(),
+                       From.Sections.end());
+  Into.Size += From.Size;
+  Into.Weight += From.Weight;
+  From.Sections.clear();
+  From.Size = 0;
+  From.Weight = 0;
+}
+
+// Group InputSections into clusters using the Call-Chain Clustering heuristic
+// then sort the clusters by density.
+void CallGraphSort::groupClusters() {
+  std::vector<int> SortedSecs(Clusters.size());
+  std::vector<Cluster *> SecToCluster(Clusters.size());
+
+  for (int SI = 0, SE = Clusters.size(); SI != SE; ++SI) {
+    SortedSecs[SI] = SI;
+    SecToCluster[SI] = &Clusters[SI];
+  }
+
+  std::stable_sort(SortedSecs.begin(), SortedSecs.end(), [&](int A, int B) {
+    return Clusters[B].getDensity() < Clusters[A].getDensity();
+  });
+
+  for (int SI : SortedSecs) {
+    Cluster &C = *SecToCluster[SI];
+
+    int BestPred = -1;
+    uint64_t BestWeight = 0;
+
+    for (Edge &E : Clusters[SI].Preds) {
+      if (BestPred == -1 || E.Weight > BestWeight) {
+        BestPred = E.From;
+        BestWeight = E.Weight;
+      }
+    }
+
+    if (BestPred == -1)
+      continue;
+
+    // don't consider merging if the edge is unlikely.
+    if (BestWeight * 10 <= C.InitialWeight)
+      continue;
+
+    Cluster *PredC = SecToCluster[BestPred];
+    if (PredC == nullptr || PredC == &C)
+      continue;
+
+    if (C.Size + PredC->Size > MAX_CLUSTER_SIZE)
+      continue;
+
+    if (isNewDensityBad(*PredC, C))
+      continue;
+
+    // NOTE: Consider using a disjoint-set to track section -> cluster mapping
+    // if this is ever slow.
+    for (int SI : C.Sections)
+      SecToCluster[SI] = PredC;
+
+    mergeClusters(*PredC, C);
+  }
+
+  // Remove empty or dead nodes.
+  Clusters.erase(std::remove_if(Clusters.begin(), Clusters.end(),
+                                [](const Cluster &C) {
+                                  return C.Size == 0 || C.Sections.empty();
+                                }),
+                 Clusters.end());
+
+  // Sort by density. Invalidates all NodeIndexs.
+  std::sort(Clusters.begin(), Clusters.end(),
+            [](const Cluster &A, const Cluster &B) {
+              return A.getDensity() > B.getDensity();
+            });
+}
+
+DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
+  groupClusters();
+
+  // Generate order.
+  llvm::DenseMap<const InputSectionBase *, int> OrderMap;
+  ssize_t CurOrder = 1;
+
+  for (const Cluster &C : Clusters)
+    for (int SecIndex : C.Sections)
+      OrderMap[Sections[SecIndex]] = 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³ huristic. All clusters are then sorted by a density
+// metric to further improve locality.
+DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
+  return CallGraphSort().run();
+}

ELF/Config.h

 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/Endian.h"
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class InputFile;
+class InputSectionBase;
 
 enum ELFKind {
   ELFNoneKind,
   ELF32LEKind,
   ELF32BEKind,
   ELF64LEKind,
   ELF64BEKind
 };
struct Configuration {
   std::vector<llvm::StringRef> FilterList;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> SymbolOrderingFile;
   std::vector<llvm::StringRef> Undefined;
   std::vector<SymbolVersion> DynamicList;
   std::vector<SymbolVersion> VersionScriptGlobals;
   std::vector<SymbolVersion> VersionScriptLocals;
   std::vector<uint8_t> BuildIdVector;
+  llvm::MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
+                  uint64_t>
+      CallGraphProfile;
   bool AllowMultipleDefinition;
   bool AndroidPackDynRelocs = false;
   bool ARMHasBlx = false;
   bool ARMHasMovtMovw = false;
   bool ARMJ1J2BranchEncoding = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;

ELF/Driver.cpp

getBuildId(opt::InputArgList &Args) {
   if (S.startswith("0x"))
     return {BuildIdKind::Hexstring, parseHex(S.substr(2))};
 
   if (S != "none")
     error("unknown --build-id style: " + S);
   return {BuildIdKind::None, {}};
 }
 
+static void readCallGraph(MemoryBufferRef MB) {
+  // Build a map from symbol name to section
+  DenseMap<StringRef, const Symbol *> SymbolNameToSymbol;
+  for (InputFile *File : ObjectFiles)
+    for (Symbol *Sym : File->getSymbols())
+      SymbolNameToSymbol[Sym->getName()] = Sym;
+
+  for (StringRef L : args::getLines(MB)) {
+    SmallVector<StringRef, 3> Fields;
+    L.split(Fields, ' ');
+    if (Fields.size() != 3)
+      fatal("parse error");
+    uint64_t Count;
+    if (!to_integer(Fields[2], Count))
+      fatal("parse error");
+    const Symbol *FromSym = SymbolNameToSymbol.lookup(Fields[0]);
+    const Symbol *ToSym = SymbolNameToSymbol.lookup(Fields[1]);
+    if (Config->WarnSymbolOrdering) {
+      if (!FromSym)
+        warn("call graph file: no such symbol: " + Fields[0]);
+      if (!ToSym)
+        warn("call graph file: no such symbol: " + Fields[1]);
+    }
+    if (!FromSym || !ToSym || Count == 0)
+      continue;
+    warnUnorderableSymbol(FromSym);
+    warnUnorderableSymbol(ToSym);
+    const Defined *FromSymD = dyn_cast<Defined>(FromSym);
+    const Defined *ToSymD = dyn_cast<Defined>(ToSym);
+    if (!FromSymD || !ToSymD)
+      continue;
+    const auto *FromSB = dyn_cast_or_null<InputSectionBase>(FromSymD->Section);
+    const auto *ToSB = dyn_cast_or_null<InputSectionBase>(ToSymD->Section);
+    if (!FromSB || !ToSB)
+      continue;
+    Config->CallGraphProfile[std::make_pair(FromSB, ToSB)] += Count;
+  }
+}
+
 static bool getCompressDebugSections(opt::InputArgList &Args) {
   StringRef S = Args.getLastArgValue(OPT_compress_debug_sections, "none");
   if (S == "none")
     return false;
   if (S != "zlib")
     error("unknown --compress-debug-sections value: " + S);
   if (!zlib::isAvailable())
     error("--compress-debug-sections: zlib is not available");
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // and identical code folding.
   markLive<ELFT>();
   demoteSharedSymbols<ELFT>();
   decompressSections();
   mergeSections();
   if (Config->ICF)
     doIcf<ELFT>();
 
+  // Read the callgraph now that we know what was gced or icfed
+  if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
+    if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
+      readCallGraph(*Buffer);
+
   // Write the result to the file.
   writeResult<ELFT>();
 }

ELF/Options.td

 defm apply_dynamic_relocs: B<"apply-dynamic-relocs",
     "Apply dynamic relocations to place",
     "Do not apply dynamic relocations to place">;
 
 defm as_needed: B<"as-needed",
     "Only set DT_NEEDED for shared libraries if used",
     "Always set DT_NEEDED for shared libraries">;
 
+defm call_graph_ordering_file: Eq<"call-graph-ordering-file">,
+  HelpText<"Layout sections to optimize the given callgraph">;
+
 // -chroot doesn't have a help text because it is an internal option.
 defm chroot: Eq<"chroot">;
 
 def color_diagnostics: F<"color-diagnostics">,
   HelpText<"Use colors in diagnostics">;
 
 def color_diagnostics_eq: J<"color-diagnostics=">,
   HelpText<"Use colors in diagnostics">;

ELF/Symbols.h

void replaceSymbol(Symbol *S, ArgT &&... Arg) {
   S->CanInline = Sym.CanInline;
   S->Traced = Sym.Traced;
 
   // Print out a log message if --trace-symbol was specified.
   // This is for debugging.
   if (S->Traced)
     printTraceSymbol(S);
 }
+
+void warnUnorderableSymbol(const Symbol *Sym);
 } // namespace elf
 
 std::string toString(const elf::Symbol &B);
 } // namespace lld
 
 #endif

ELF/Symbols.cpp

void elf::printTraceSymbol(Symbol *Sym) {
   else if (dyn_cast_or_null<BssSection>(cast<Defined>(Sym)->Section))
     S = ": common definition of ";
   else
     S = ": definition of ";
 
   message(toString(Sym->File) + S + Sym->getName());
 }
 
+void elf::warnUnorderableSymbol(const Symbol *Sym) {
+  if (!Config->WarnSymbolOrdering)
+    return;
+  const InputFile *File = Sym->File;
+  auto *D = dyn_cast<Defined>(Sym);
+  if (Sym->isUndefined())
+    warn(toString(File) +
+         ": unable to order undefined symbol: " + Sym->getName());
+  else if (Sym->isShared())
+    warn(toString(File) + ": unable to order shared symbol: " + Sym->getName());
+  else if (D && !D->Section)
+    warn(toString(File) +
+         ": unable to order absolute symbol: " + Sym->getName());
+  else if (D && isa<OutputSection>(D->Section))
+    warn(toString(File) +
+         ": unable to order synthetic symbol: " + Sym->getName());
+  else if (D && !D->Section->Repl->Live)
+    warn(toString(File) +
+         ": unable to order discarded symbol: " + Sym->getName());
+}
+
 // Returns a symbol for an error message.
 std::string lld::toString(const Symbol &B) {
   if (Config->Demangle)
     if (Optional<std::string> S = demangleItanium(B.getName()))
       return *S;
   return B.getName();
 }

ELF/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
 #include "AArch64ErrataFix.h"
+#include "CallGraphSort.h"
 #include "Config.h"
 #include "Filesystem.h"
 #include "LinkerScript.h"
 #include "MapFile.h"
 #include "OutputSections.h"
 #include "Relocations.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
findOrphanPos(std::vector<BaseCommand *>::iterator B,
   while (I != E && shouldSkip(*I))
     ++I;
   return I;
 }
 
 // Builds section order for handling --symbol-ordering-file.
 static DenseMap<const InputSectionBase *, int> buildSectionOrder() {
   DenseMap<const InputSectionBase *, int> SectionOrder;
+  // Use the rarely used option -call-graph-ordering-file to sort sections.
+  if (!Config->CallGraphProfile.empty())
+    return computeCallGraphProfileOrder();
+
   if (Config->SymbolOrderingFile.empty())
     return SectionOrder;
 
   struct SymbolOrderEntry {
     int Priority;
     bool Present;
   };
 
   // Build a map from symbols to their priorities. Symbols that didn't
   // appear in the symbol ordering file have the lowest priority 0.
   // All explicitly mentioned symbols have negative (higher) priorities.
   DenseMap<StringRef, SymbolOrderEntry> SymbolOrder;
   int Priority = -Config->SymbolOrderingFile.size();
   for (StringRef S : Config->SymbolOrderingFile)
     SymbolOrder.insert({S, {Priority++, false}});
 
   // Build a map from sections to their priorities.
   auto AddSym = [&](Symbol &Sym) {
     auto It = SymbolOrder.find(Sym.getName());
     if (It == SymbolOrder.end())
       return;
     SymbolOrderEntry &Ent = It->second;
     Ent.Present = true;
 
-    if (Config->WarnSymbolOrdering) {
-      auto *D = dyn_cast<Defined>(&Sym);
-      InputFile *File = Sym.File;
-      if (Sym.isUndefined())
-        warn(toString(File) +
-             ": unable to order undefined symbol: " + Sym.getName());
-      else if (Sym.isShared())
-        warn(toString(File) +
-             ": unable to order shared symbol: " + Sym.getName());
-      else if (D && !D->Section)
-        warn(toString(File) +
-             ": unable to order absolute symbol: " + Sym.getName());
-      else if (D && isa<OutputSection>(D->Section))
-        warn(toString(File) +
-             ": unable to order synthetic symbol: " + Sym.getName());
-      else if (D && !D->Section->Repl->Live)
-        warn(toString(File) +
-             ": unable to order discarded symbol: " + Sym.getName());
-    }
+    warnUnorderableSymbol(&Sym);
 
     if (auto *D = dyn_cast<Defined>(&Sym)) {
       if (auto *Sec = dyn_cast_or_null<InputSectionBase>(D->Section)) {
         int &Priority = SectionOrder[cast<InputSectionBase>(Sec->Repl)];
         Priority = std::min(Priority, Ent.Priority);
       }
     }
   };

test/ELF/cgprofile-icf.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: echo "A B 100" > %t.call_graph
+# RUN: echo "A C 40" >> %t.call_graph
+# RUN: echo "C D 61" >> %t.call_graph
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph -o %t.out -icf=all
+# RUN: llvm-readobj -symbols %t.out | FileCheck %s
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph -o %t2.out
+# RUN: llvm-readobj -symbols %t2.out | FileCheck %s --check-prefix=NOICF
+
+    .section    .text.D,"ax",@progbits
+    .globl  D
+D:
+    mov $60, %rax
+    retq
+
+    .section    .text.C,"ax",@progbits
+    .globl  C
+C:
+    mov $60, %rax
+    retq
+
+    .section    .text.B,"ax",@progbits
+    .globl  B
+B:
+    mov $2, %rax
+    retq
+
+    .section    .text.A,"ax",@progbits
+    .globl  A
+A:
+    mov $42, %rax
+    retq
+
+# CHECK:          Name: A
+# CHECK-NEXT:     Value: 0x201000
+# CHECK:          Name: B
+# CHECK-NEXT:     Value: 0x201010
+# CHECK:          Name: C
+# CHECK-NEXT:     Value: 0x201008
+# CHECK:          Name: D
+# CHECK-NEXT:     Value: 0x201008
+
+# NOICF:          Name: A
+# NOICF-NEXT:     Value: 0x201000
+# NOICF:          Name: B
+# NOICF-NEXT:     Value: 0x201008
+# NOICF:          Name: C
+# NOICF-NEXT:     Value: 0x201010
+# NOICF:          Name: D
+# NOICF-NEXT:     Value: 0x201018

test/ELF/cgprofile-txt.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld -e A %t -o %t2
+# RUN: llvm-readobj -symbols %t2 | FileCheck %s --check-prefix=NOSORT
+
+# RUN: echo "A B 10" > %t.call_graph
+# RUN: echo "A B 10" >> %t.call_graph
+# RUN: echo "Aa B 80" >> %t.call_graph
+# RUN: echo "A C 40" >> %t.call_graph
+# RUN: echo "B C 30" >> %t.call_graph
+# RUN: echo "C D 90" >> %t.call_graph
+# RUN: echo "PP TS 100" >> %t.call_graph
+# RUN: echo "_init2 _init 24567837" >> %t.call_graph
+# RUN: echo "TS QC 9001" >> %t.call_graph
+# RUN: echo "TooManyPreds0 TooManyPreds 10" >> %t.call_graph
+# RUN: echo "TooManyPreds1 TooManyPreds 10" >> %t.call_graph
+# RUN: echo "TooManyPreds2 TooManyPreds 10" >> %t.call_graph
+# 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: llvm-readobj -symbols %t2 | FileCheck %s
+
+    .section    .text.D,"ax",@progbits
+D:
+    retq
+
+    .section    .text.C,"ax",@progbits
+    .globl  C
+C:
+    retq
+
+    .section    .text.B,"ax",@progbits
+    .globl  B
+B:
+    retq
+
+    .section    .text.A,"ax",@progbits
+    .globl  A
+A:
+Aa:
+    retq
+
+    .section    .ponies,"ax",@progbits,unique,1
+    .globl TS
+TS:
+    retq
+
+    .section    .ponies,"ax",@progbits,unique,2
+    .globl PP
+PP:
+    retq
+
+    .section    .other,"ax",@progbits,unique,1
+    .globl QC
+QC:
+    retq
+
+    .section    .other,"ax",@progbits,unique,2
+    .globl GB
+GB:
+    retq
+
+    .section    .init,"ax",@progbits,unique,1
+    .globl _init
+_init:
+    retq
+
+    .section    .init,"ax",@progbits,unique,2
+    .globl _init2
+_init2:
+    retq
+
+    .section    .text.TooManyPreds,"ax",@progbits
+TooManyPreds:
+    retq
+  retq
+  retq
+  retq
+  retq
+  retq
+  retq
+  retq
+  retq
+  retq
+
+    .section    .text.TooManyPreds0,"ax",@progbits
+TooManyPreds0:
+    retq
+
+    .section    .text.TooManyPreds1,"ax",@progbits
+TooManyPreds1:
+    retq
+
+    .section    .text.TooManyPreds2,"ax",@progbits
+TooManyPreds2:
+    retq
+
+    .section    .text.TooManyPreds3,"ax",@progbits
+TooManyPreds3:
+    retq
+
+    .section    .text.TooManyPreds4,"ax",@progbits
+TooManyPreds4:
+    retq
+
+    .section    .text.TooManyPreds5,"ax",@progbits
+TooManyPreds5:
+    retq
+
+    .section    .text.TooManyPreds6,"ax",@progbits
+TooManyPreds6:
+    retq
+
+    .section    .text.TooManyPreds7,"ax",@progbits
+TooManyPreds7:
+    retq
+
+    .section    .text.TooManyPreds8,"ax",@progbits
+TooManyPreds8:
+    retq
+
+    .section    .text.TooManyPreds9,"ax",@progbits
+TooManyPreds9:
+    retq
+
+    .section    .text.TooManyPreds10,"ax",@progbits
+TooManyPreds10:
+    retq
+
+# CHECK:          Name: D
+# CHECK-NEXT:     Value: 0x201003
+# CHECK:          Name: TooManyPreds
+# CHECK-NEXT:     Value: 0x201004
+# CHECK:          Name: TooManyPreds10
+# CHECK-NEXT:     Value: 0x201018
+# CHECK:          Name: A
+# CHECK-NEXT:     Value: 0x201000
+# CHECK:          Name: B
+# CHECK-NEXT:     Value: 0x201001
+# CHECK:          Name: C
+# CHECK-NEXT:     Value: 0x201002
+# CHECK:          Name: GB
+# CHECK-NEXT:     Value: 0x20101F
+# CHECK:          Name: PP
+# CHECK-NEXT:     Value: 0x20101C
+# CHECK:          Name: QC
+# CHECK-NEXT:     Value: 0x20101E
+# CHECK:          Name: TS
+# CHECK-NEXT:     Value: 0x20101D
+# CHECK:          Name: _init
+# CHECK-NEXT:     Value: 0x201020
+# CHECK:          Name: _init2
+# CHECK-NEXT:     Value: 0x201021
+
+# NOSORT:          Name: D
+# NOSORT-NEXT:     Value: 0x201000
+# NOSORT:          Name: TooManyPreds
+# NOSORT-NEXT:     Value: 0x201004
+# NOSORT:          Name: TooManyPreds10
+# NOSORT-NEXT:     Value: 0x201018
+# NOSORT:          Name: A
+# NOSORT-NEXT:     Value: 0x201003
+# NOSORT:          Name: B
+# NOSORT-NEXT:     Value: 0x201002
+# NOSORT:          Name: C
+# NOSORT-NEXT:     Value: 0x201001
+# NOSORT:          Name: GB
+# NOSORT-NEXT:     Value: 0x20101C
+# NOSORT:          Name: PP
+# NOSORT-NEXT:     Value: 0x20101A
+# NOSORT:          Name: QC
+# NOSORT-NEXT:     Value: 0x20101B
+# NOSORT:          Name: TS
+# NOSORT-NEXT:     Value: 0x201019
+# NOSORT:          Name: _init
+# NOSORT-NEXT:     Value: 0x20101D
+# NOSORT:          Name: _init2
+# NOSORT-NEXT:     Value: 0x20101E

test/ELF/cgprofile-warn.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: echo "A B 100" > %t.call_graph
+# RUN: echo "A C 40" >> %t.call_graph
+# RUN: echo "B C 30" >> %t.call_graph
+# RUN: echo "adena A 30" >> %t.call_graph
+# RUN: echo "poppy A 30" >> %t.call_graph
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph -o %t.out \
+# RUN:   -noinhibit-exec -icf=all 2>&1 | FileCheck %s
+
+    .section    .text.C,"ax",@progbits
+    .globl  C
+C:
+    mov poppy, %rax
+    retq
+
+B = 0x1234
+
+    .section    .text.A,"ax",@progbits
+    .globl  A
+A:
+    mov poppy, %rax
+    retq
+
+# CHECK: unable to order absolute symbol: B
+# CHECK: call graph file: no such symbol: adena
+# CHECK: unable to order undefined symbol: poppy