[lld][ELF] Add profile guided section layout

[Bigcheese]

Summary

This adds profile guided layout using the Call-Chain Clustering (C³) heuristic from https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf .

RFC: [llvm-dev] [RFC] Profile guided section layout http://lists.llvm.org/pipermail/llvm-dev/2017-June/114178.html

[ruiu]

ELF/Writer.cpp

930–936 ↗

(On Diff #113947)

for (BaseCommand *Base : Script->Opt.Commands)
  if (auto *OS = dyn_cast<OutputSection>(Base))
    if (OS->Name == ".text")
      OS->sort([&](InputSectionBase *IS) { return OrderMap.lookup(IS); });

[pcc]

In D36351#863961, @ruiu wrote:

How can I test this? I wonder how to create profiling data to feed this feature.

I have a local patch to AutoFDO that I use to create profiles. I can upload it somewhere if you'd like.

[ruiu]

I have a local patch to AutoFDO that I use to create profiles. I can upload it somewhere if you'd like.

Thanks. But the paper says that they used perf command to get profiling data. Why did you have to use AutoFDO?

[pcc]

In D36351#863966, @ruiu wrote:

I have a local patch to AutoFDO that I use to create profiles. I can upload it somewhere if you'd like.

Thanks. But the paper says that they used perf command to get profiling data. Why did you have to use AutoFDO?

As far as I know the missing piece is a tool that converts LBR data collected by perf into a weighted call graph. AutoFDO already has support for creating weighted call graphs from perf LBR data, so I just needed to teach it to output the graph in a different format.

[ruiu]

I'd think I want to make lld able to directly parse a perf command output so that users can try this feature easily.

[pcc]

In D36351#864001, @pcc wrote:

In D36351#863966, @ruiu wrote:

I have a local patch to AutoFDO that I use to create profiles. I can upload it somewhere if you'd like.

Thanks. But the paper says that they used perf command to get profiling data. Why did you have to use AutoFDO?

As far as I know the missing piece is a tool that converts LBR data collected by perf into a weighted call graph. AutoFDO already has support for creating weighted call graphs from perf LBR data, so I just needed to teach it to output the graph in a different format.

Here is my patched copy of autofdo: https://github.com/pcc/autofdo/tree/lld-cgprofile

Once you've built it, you can use it like this:

perf record --pfm-events=br_inst_retired:near_taken -b ./your_binary
/path/to/create_lld_profile -binary ./your_binary perf.data

Then the profile will be in cgprofile.txt.

[Bigcheese]

Address review comments.

[ruiu]

Could you send me a patch to produce a call graph file so that I can try this patch on my machine?

ELF/CallGraphSort.cpp

99–101 ↗

(On Diff #114448)

You can just return To < Other.To.

127 ↗

(On Diff #114448)

This loop is a bit too dense. It cannot be understood without reading each line carefully as I don't understand the whole picture. Please insert a blank line between code blocks. Adding more comment would help.

128 ↗

(On Diff #114448)

Please define local variables for C.first.first, C.first.second and C.second so that they are accessed through meaningful names.

130–135 ↗

(On Diff #114448)

auto -> auto *

147 ↗

(On Diff #114448)

nit: add {}

153 ↗

(On Diff #114448)

Please add a function comment as to what this function is intended to do. I do not understand this function because I don't get a whole picture.

158–163 ↗

(On Diff #114448)

Add blank lines before comments.

165–166 ↗

(On Diff #114448)

Please remove debug code.

178–180 ↗

(On Diff #114448)

This looks odd. Why do you need to do this? I think you can just leave it alone.

207–208 ↗

(On Diff #114448)

This might be understood for those who read the paper, but I don't think that is enough. Please write more comment as to what are clusters, what is density, and what is the heuristic.

272–273 ↗

(On Diff #114448)

You can do this in one line without defining a local variable.

ELF/Writer.cpp

926–928 ↗

(On Diff #114448)

I'd factor this code out as OutputSection *findOutputSection(StringRef Name).

[davide]

ELF/CallGraphSort.cpp

112 ↗

(On Diff #114448)

Simbol Bodies.

117 ↗

(On Diff #114448)

why std::map and not densemap?
if there's a reason, add a comment.

119 ↗

(On Diff #114448)

is the explicit return needed here?

130 ↗

(On Diff #114448)

auto * presumably?

186 ↗

(On Diff #114448)

Can you guarantee determinism of the output if two sort implementations break ties in different ways?

189 ↗

(On Diff #114448)

std::unique?

241 ↗

(On Diff #114448)

node indices (I don't think indexes is a word).

[davide]

ELF/CallGraphSort.cpp

112 ↗

(On Diff #114448)

*symbol bodies

[zturner]

Not sure what the status of this is, but it would be realllly cool if we could get this in before the 6.0 release branch, which I think is only a few weeks away.

[Bigcheese]

Fix priority queue bugs.

[ruiu]

This is perhaps a fundamental question, but why do you compute the layout in the linker? It looks like you could create an external tool that computes a desired layout and outputs it as a symbol ordering file.

lld/ELF/CallGraphSort.cpp

62–95

Since CallGraphSort class is local to this file anyway, I don't see a reason to make these classes inside CallGraphSort. You could move this outside of CallGraphSort (but still inside the anonymous namespace) to remove an extra level of namespace.

100

ArrayRef is preferred over std::vector<T>&

106–107

priority -> Priority

priority_lookup -> PriorityLookup

115–119

Usually we write public members before private members.

124–125

Sections is always empty, no? Why don't you do

CallGraphSort::Node::Node(const InputSectionBase *IS) : Sections(IS), Size(IS->getSize()) {}

?

162

Since Config->CallGraphProfile is available here, you don't need to pass it as an argument.

217

Use ArrayRef.

lld/ELF/Driver.cpp

581

Remove this trailing empty comment line.

1059

Directly use getLastArg(OPT_call_graph_profile_file) and remove Config->CallGraphProfileFile.

lld/ELF/Options.td

54–58

I think these two options should be merged into one option which takes a filename as an argument and enables the feature.

llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp

126–142

Debug code?

llvm/lib/Transforms/Instrumentation/CFGProfile.cpp

96–99

Indentation

llvm/tools/llvm-readobj/ELFDumper.cpp

3422

Please use clang-format.

4032

80 cols

[Bigcheese]

This needs to be implemented in the linker because of the line:

if (From.Size + To.Size > Target->PageSize)
  continue;

This is responsible for doubling the performance improvement on a game. Implementing this outside of the linker requires implementing most of the linker, including LTO.

lld/ELF/CallGraphSort.cpp

124–125

Because Sections(IS) isn't valid?

162

This class currently uses zero global state. I'd prefer not to add any for no gain.

217

FE is used as a std::vector here. Replacing with ArrayRef would not work.

lld/ELF/Options.td

54–58

A text file is not the only way to get input for sorting. The input can also come from object files.

[Bigcheese]

Address review comments.

[ruiu]

This needs to be implemented in the linker because of the line:

if (From.Size + To.Size > Target->PageSize)
  continue;

This is responsible for doubling the performance improvement on a game. Implementing this outside of the linker requires implementing most of the linker, including LTO.

And function sizes cannot be retrieved from the instrumented build (because instrumentation changes function size), so it must be computed at link-time. Is this correct?

[ruiu]

lld/ELF/Options.td

54–58

Yeah, that actually confused me. How a compiler can add information related to profiling data to an object file being generated? I don't think I understand how the new .note section works.

[Bigcheese]

In D36351#956212, @ruiu wrote:

This needs to be implemented in the linker because of the line:

if (From.Size + To.Size > Target->PageSize)
  continue;

This is responsible for doubling the performance improvement on a game. Implementing this outside of the linker requires implementing most of the linker, including LTO.

And function sizes cannot be retrieved from the instrumented build (because instrumentation changes function size), so it must be computed at link-time. Is this correct?

Yes.

[Bigcheese]

lld/ELF/Options.td

54–58

When you do -fprofile-instr-use=<path> the compiler adds profile data from that file to the IR as metadat. The cgprofile pass uses that metadata to generate metadata for the call graph profile. It then writes that to the object file.

[Bigcheese]

lld/ELF/Options.td

54–58

To clarify. Where the compiler reads -fprofile-instr-use=<path> is the only place the profile data can be read. It depends on the exact state of the IR at that point in translation. You can't just pass the profile data to the linker or some other tool and have it make sense of it. The cgprofile pass runs after all other IR level optimization. These other optimization passes keep the branch frequency info (BFI) metadata up to date with CFG and CG changes. The cgprofile pass uses BFI to compute the actual call graph profile. This has to be communicated to the linker somehow, so it gets written to the object file.

[ruiu]

Then I wonder why you need to pass a profile data to the linker as a text file in the first place. Does the data embedded to an object file lack something, like inter-compilation-unit call frequency?

[ruiu]

lld/ELF/CallGraphSort.cpp

59–60

nit: move this out of the anonymous namespace.

195–197

This means that an input file could contain more than one line for the same from-to symbol pair. But does that actually happen?

[ruiu]

lld/ELF/CallGraphSort.cpp

209

How can the graph have a self edge?

214–216

This assertion doesn't make make sense to me -- if WorkLookup.find(CEI) == WorkLookup.end(), then std::find(WorkQueue.begin(), WorkQueue.end(), CEI) == WorkQueue.end() should be trivially true which can't be broken.

242

We don't care about micro managing memory consumption in lld. If you need to erase elements not for saving memory but for other reason, please use erase().

249–250

Can't this just be std::sort(FE.begin(), FE.end())?

258

It seems you are not actually removing Result.

264–265

Remove.

268–269

Remove

280

nit: please add {}

293

Please expand this comment. In particular, please describe what WorkLookup and WorkQueue are expected to have. Looks like I can't understand the code without it.

[Bigcheese]

In D36351#957139, @ruiu wrote:

Then I wonder why you need to pass a profile data to the linker as a text file in the first place. Does the data embedded to an object file lack something, like inter-compilation-unit call frequency?

The text file is a separate way to get the call graph profile into the linker. @rafael wanted to do that as a first pass to simplify the patch, but you wanted to see the full thing.

[ruiu]

I wonder what was a motivation to implement two different ways to do one thing.

[Bigcheese]

lld/ELF/CallGraphSort.cpp

195–197

This actually means that multiple symbols could be in the same section.

209

Two symbols which are in the same section.

214–216

It's not trivially true. WorkLookup and WorkQueue are manually maintained and edges are constantly changed. This is to ensure that they are kept in sync.

242

Pretty sure we care about N^2 memory usage.

249–250

No.

[Bigcheese]

In D36351#957474, @ruiu wrote:

I wonder what was a motivation to implement two different ways to do one thing.

There are other ways to generate a call graph profile. dtrace for example. I don't particularly care about the text format as you can always generate an object file that only contains profile data, but it is a lot easier to generate the text file.

[ruiu]

lld/ELF/CallGraphSort.cpp

209

Can you elaborate? I'm trying to understand it, so giving me just an answer isn't that helpful to me.

249–250

Why?

[ruiu]

I did not request you to upload a patch which contains both LLVM and lld changes, but I didn't intend to put everything in one patch. I wouldn't add the text file and the object file profiling data at the same time in the initial patch. It doesn't sound like you are not sure if you need the text file support. I would drop the text file support then.

[ruiu]

Apologies. I meant I did request you to upload a patch which contains ...

[Bigcheese]

lld/ELF/CallGraphSort.cpp

209

Given an object file which contains a .text section and two symbols, A and B, which point to that section. And given the following profile:

A -> B 1000

The code in CallGraphSort::CallGraphSort will generate a graph with one node and one edge:

Nodes:
  - index: 0
    weight: 1000
Edges:
  - from: 0
    to: 0
    weight: 1000

This correctly gives node[0] a weight of 1000 which is needed for the final sort by density.

CallGraphSort::CallGraphSort could skip adding self edges which would remove the need for this. I'll do that.

249–250

Because the following code merges consecutive equal edges to remove duplicate edges. FE is a list of edges indices, not edges.

[Bigcheese]

I've simplified the logic by getting rid of WorkLookup and just embedding the std::set iterator in Edge.

I've also split off the LLVM changes into two separate reviews:

• https://reviews.llvm.org/D42161
• https://reviews.llvm.org/D42163

[Bigcheese]

Changed to testcase from paper.

[Bigcheese]

• Order all sections and add a test
• Simplified
• Remove unused include

[Bigcheese]

• Don't reorder non-reorderable sections
• Skip edges across output sections
• Add tests

[Bigcheese]

• Update to top of tree.
• Add some comments.

[pdeng6]

@Bigcheese

I'm trying function layout methodologies within ChromeOS to improve chrome performance, this feature is very important since the work relies on it.
I've checked out the patches for both lld(https://reviews.llvm.org/D36351?id=133550) and llvm(https://reviews.llvm.org/D42161 and https://reviews.llvm.org/D42163), and built it locally, but I'm afraid the patches for llvm is not as fresh as that for lld.
Would it be possible for you to show the latest patches at both side, and the base llvm/lld revisions you are working on? then we can completely align the environment.

thanks
Pan

[Bigcheese]

Rewrote the algorithm to match hfsort. Now gets the same performance as hfsort in Rafael's testcase.

[Bigcheese]

Address review comments.

[• rafael]

Rafael Avila de Espindola <[e-mail]> writes:

+ InputSectionBase *FromSec = SymbolSection.lookup(Fields[0]);
+ InputSectionBase *ToSec = SymbolSection.lookup(Fields[1]);
+ if (FromSec && ToSec)
+ Config->CallGraphProfile[std::make_pair(FromSec, ToSec)] = Count;

This should be "+=", no? If there are multiple calls from one section to
another I would expect us to use the total in the graph.

Looks like the missing + gets us the last missing performance bits.

In the attached log "old" is a rebased version of your previous patch, "new"
is your current patch and "new-new" is your current patch with the above
fix.

• results.txt6 KBDownload
• msg-17485-242.txt20 BDownload

[• rafael]

Ah, and please git-clang-format :-)

Cheers,
Rafael

Michael Spencer via Phabricator via llvm-commits
<[e-mail]> writes:

Bigcheese updated this revision to Diff 137040.
Bigcheese added a comment.

Rewrote the algorithm to match hfsort. Now gets the same performance as hfsort in Rafael's testcase.

https://reviews.llvm.org/D36351

Files:

ELF/CMakeLists.txt
ELF/CallGraphSort.cpp
ELF/CallGraphSort.h
ELF/Config.h
ELF/Driver.cpp
ELF/Options.td
ELF/Writer.cpp
test/ELF/cgprofile-txt.s

Index: test/ELF/cgprofile-txt.s

• /dev/null

+++ test/ELF/cgprofile-txt.s
@@ -0,0 +1,106 @@
+# 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 100" > %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: 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:
+ 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
+
+# CHECK: Name: D
+# CHECK-NEXT: Value: 0x201003
+# 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: 0x201007
+# CHECK: Name: PP
+# CHECK-NEXT: Value: 0x201004
+# CHECK: Name: QC
+# CHECK-NEXT: Value: 0x201006
+# CHECK: Name: TS
+# CHECK-NEXT: Value: 0x201005
+# CHECK: Name: _init
+# CHECK-NEXT: Value: 0x201008
+# CHECK: Name: _init2
+# CHECK-NEXT: Value: 0x201009
+
+# NOSORT: Name: D
+# NOSORT-NEXT: Value: 0x201000
+# 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: 0x201007
+# NOSORT: Name: PP
+# NOSORT-NEXT: Value: 0x201005
+# NOSORT: Name: QC
+# NOSORT-NEXT: Value: 0x201006
+# NOSORT: Name: TS
+# NOSORT-NEXT: Value: 0x201004
+# NOSORT: Name: _init
+# NOSORT-NEXT: Value: 0x201008
+# NOSORT: Name: _init2
+# NOSORT-NEXT: Value: 0x201009

Index: ELF/Writer.cpp

• ELF/Writer.cpp

+++ ELF/Writer.cpp
@@ -9,6 +9,7 @@

#include "Writer.h"
#include "AArch64ErrataFix.h"
+#include "CallGraphSort.h"
#include "Config.h"
#include "Filesystem.h"
#include "LinkerScript.h"
@@ -1110,6 +1111,14 @@
If no layout was provided by linker script, we want to apply default
sorting for special input sections. This also handles --symbol-ordering-file.
template <class ELFT> void Writer<ELFT>::sortInputSections() {
+ // Use the rarely used option -call-graph-ordering-file to sort sections.
+ if (!Config->CallGraphProfile.empty()) {
+ DenseMap<const InputSectionBase *, int> Order =
+ computeCallGraphProfileOrder();
+ for (BaseCommand *Base : Script->SectionCommands)
+ if (auto *Sec = dyn_cast<OutputSection>(Base))
+ sortSection(Sec, Order);
+ }

// Build the order once since it is expensive.
DenseMap<const InputSectionBase *, int> Order = buildSectionOrder();
for (BaseCommand *Base : Script->SectionCommands)

Index: ELF/Options.td

• ELF/Options.td

+++ ELF/Options.td
@@ -66,6 +66,9 @@

"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">;

Index: ELF/Driver.cpp

• ELF/Driver.cpp

+++ ELF/Driver.cpp
@@ -571,6 +571,31 @@

return {BuildIdKind::None, {}};

}

+static void readCallGraph(MemoryBufferRef MB) {
+ // Build a map from symbol name to section
+ DenseMap<StringRef, InputSectionBase *> SymbolSection;
+ for (InputFile *File : ObjectFiles)
+ for (Symbol *Sym : File->getSymbols())
+ if (auto *D = dyn_cast<Defined>(Sym))
+ if (auto *IS = dyn_cast_or_null<InputSectionBase>(D->Section))
+ SymbolSection[D->getName()] = IS;
+
+ std::vector<StringRef> Lines = args::getLines(MB);
+ for (StringRef L : Lines) {
+ 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");
+ InputSectionBase *FromSec = SymbolSection.lookup(Fields[0]);
+ InputSectionBase *ToSec = SymbolSection.lookup(Fields[1]);
+ if (FromSec && ToSec)
+ Config->CallGraphProfile[std::make_pair(FromSec, ToSec)] = Count;
+ }
+}
+
static bool getCompressDebugSections(opt::InputArgList &Args) {

StringRef S = Args.getLastArgValue(OPT_compress_debug_sections, "none");
if (S == "none")

@@ -1118,6 +1143,10 @@

// Apply symbol renames for -wrap.
Symtab->applySymbolWrap();

+ if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
+ if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
+ readCallGraph(*Buffer);
+

// Now that we have a complete list of input files.
// Beyond this point, no new files are added.
// Aggregate all input sections into one place.

Index: ELF/Config.h

• ELF/Config.h

+++ ELF/Config.h
@@ -24,6 +24,7 @@
namespace elf {

class InputFile;
+class InputSectionBase;

enum ELFKind {

ELFNoneKind,

@@ -103,6 +104,9 @@

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;

Index: ELF/CallGraphSort.h

• /dev/null

+++ ELF/CallGraphSort.h
@@ -0,0 +1,23 @@
+===- 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

Index: ELF/CallGraphSort.cpp

• /dev/null

+++ ELF/CallGraphSort.cpp
@@ -0,0 +1,350 @@
+===- 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 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"
+
+#include "llvm/Support/MathExtras.h"
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::elf;
+
+namespace {
+using ClusterIndex = std::ptrdiff_t;
+using SectionIndex = std::ptrdiff_t;
+using EdgeIndex = std::ptrdiff_t;
+
+ Used for calculating an comparing density. Use soft-float for determinism.
+struct Double : APFloat {
+ Double() : APFloat(APFloat::IEEEdouble(), 0) {}
+ Double(uint64_t Val) : APFloat(APFloat::IEEEdouble(), Val) {}
+ Double(APFloat A) : APFloat(A) {}
+ bool operator>(const Double Other) const {
+ return compare(Other) == cmpGreaterThan;
+ }
+ bool operator<(const Double Other) const {
+ return compare(Other) == cmpLessThan;
+ }
+};
+
+struct Cluster {
+ Cluster(SectionIndex Sec, const InputSectionBase *IS);
+
+ Double getDensity() const {
+ if (Size == 0)
+ return 0;
+ return Double(Weight) / Double(Size);
+ }
+
+ std::vector<const InputSectionBase *> ISBs;
+ std::vector<SectionIndex> Sections;
+ int64_t Size = 0;
+ uint64_t Weight = 0;
+};
+
+struct Section {
+ Section(const InputSectionBase *IS) : ISB(IS) { Size = ISB->getSize(); }
+
+ Double getDensity() const {
+ if (Size == 0)
+ return 0;
+ return Double(Weight) / Double(Size);
+ }
+
+ int64_t Size = 0;
+ uint64_t Weight = 0;
+ const InputSectionBase *ISB;
+ std::vector<SectionIndex> Preds;
+ std::vector<SectionIndex> Succs;
+};
+
+struct Edge {
+ SectionIndex From;
+ SectionIndex To;
+ uint64_t Weight;
+ Double NormalizedWeight = 0;
+
+ bool operator==(const Edge Other) const;
+};
+
+struct EdgeDenseMapInfo {
+ static Edge getEmptyKey() {
+ return {DenseMapInfo<SectionIndex>::getEmptyKey(),
+ DenseMapInfo<SectionIndex>::getEmptyKey(), 0, 0};
+ }
+ static Edge getTombstoneKey() {
+ return {DenseMapInfo<SectionIndex>::getTombstoneKey(),
+ DenseMapInfo<SectionIndex>::getTombstoneKey(), 0, 0};
+ }
+ static unsigned getHashValue(const Edge &Val) {
+ return hash_combine(DenseMapInfo<SectionIndex>::getHashValue(Val.From),
+ DenseMapInfo<SectionIndex>::getHashValue(Val.To));
+ }
+ static bool isEqual(const Edge &LHS, const Edge &RHS) { return LHS == RHS; }
+};
+
+class CallGraphSort {
+public:
+ CallGraphSort();
+
+ DenseMap<const InputSectionBase *, int> run();
+
+private:
+ DenseMap<Edge, EdgeIndex, EdgeDenseMapInfo> EdgeMap;
+ std::vector<Cluster> Clusters;
+ std::vector<Edge> Edges;
+ std::vector<Section> Sections;
+
+ void normalizeEdgeWeights();
+ void generateClusters();
+};
+
+ 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
+
+Cluster::Cluster(SectionIndex Sec, const InputSectionBase *IS) {
+ ISBs.push_back(IS);
+ Sections.push_back(Sec);
+ Size = IS->getSize();
+}
+
+bool Edge::operator==(const Edge Other) const {
+ return From == Other.From && To == Other.To;
+}
+
+ Take the edge list in Config->CallGraphProfile, resolve symbol names to
+ Symbols, and generate a graph between InputSections with the provided
+ weights.
+CallGraphSort::CallGraphSort() {
+ MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
+ uint64_t> &Profile = Config->CallGraphProfile;
+ DenseMap<const InputSectionBase *, SectionIndex> SecToSec;
+
+ auto GetOrCreateNode = [&](const InputSectionBase *IS) -> SectionIndex {
+ auto Res = SecToSec.insert(std::make_pair(IS, Sections.size()));
+ if (Res.second)
+ Sections.emplace_back(IS);
+ return Res.first->second;
+ };
+
+ Create the graph.
+ for (const auto &C : Profile) {
+ const InputSectionBase *FromSB = C.first.first;
+ const InputSectionBase *ToSB = C.first.second;
+ uint64_t Weight = C.second;
+
+ if (Weight == 0)
+ continue;
+
+ 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;
+
+ SectionIndex From = GetOrCreateNode(FromSB);
+ SectionIndex To = GetOrCreateNode(ToSB);
+
+ Sections[To].Weight = SaturatingAdd(Sections[To].Weight, Weight);
+
+ if (From == To)
+ continue;
+
+ Edge E{From, To, Weight};
+
+ Add or increment an edge
+ auto Res = EdgeMap.insert(std::make_pair(E, Edges.size()));
+ EdgeIndex EI = Res.first->second;
+ if (Res.second) {
+ Edges.push_back(E);
+ Sections[From].Succs.push_back(To);
+ Sections[To].Preds.push_back(From);
+ } else
+ Edges[EI].Weight = SaturatingAdd(Edges[EI].Weight, Weight);
+ }
+ normalizeEdgeWeights();
+}
+
+ Normalize the edge weights so that we can reject edges which have a low
+ probibility.
+void CallGraphSort::normalizeEdgeWeights() {
+ for (SectionIndex SI = 0, SE = Sections.size(); SI != SE; ++SI) {
+ Section &S = Sections[SI];
+ for (SectionIndex PI : S.Preds) {
+ Edge &E = Edges[EdgeMap[{PI, SI, 0, 0}]];
+ if (S.Weight == 0)
+ continue;
+ E.NormalizedWeight = Double(E.Weight) / Double(S.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 (A.getDensity() >
+ NewDensity * Double(MAX_DENSITY_DEGRADATION))
+ return true;
+ return false;
+}
+
+static void mergeClusters(Cluster &Into, Cluster &From) {
+ Into.ISBs.insert(Into.ISBs.end(), From.ISBs.begin(), From.ISBs.end());
+ Into.Sections.insert(Into.Sections.end(), From.Sections.begin(),
+ From.Sections.end());
+ Into.Size += From.Size;
+ Into.Weight += From.Weight;
+ From.ISBs.clear();
+ 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::generateClusters() {
+ Minimum edge probability to consider merging.
+ const Double MIN_EDGE_PROBABILITY = Double(1) / Double(10);
+
+ std::vector<SectionIndex> SortedSecs;
+ std::vector<Cluster *> SecToCluster(Sections.size());
+
+ Clusters.reserve(Sections.size());
+
+ for (SectionIndex SI = 0, SE = Sections.size(); SI != SE; ++SI) {
+ Cluster C(SI, Sections[SI].ISB);
+ C.Size = Sections[SI].Size;
+ C.Weight = Sections[SI].Weight;
+ Clusters.push_back(C);
+ SortedSecs.push_back(SI);
+ }
+
+ for (Cluster &C : Clusters) {
+ SecToCluster[C.Sections.front()] = &C;
+ }
+
+ std::stable_sort(SortedSecs.begin(), SortedSecs.end(),
+ [&](SectionIndex A, SectionIndex B) {
+ return Sections[A].getDensity() > Sections[B].getDensity();
+ });
+
+ for (SectionIndex SI : SortedSecs) {
+ Cluster &C = *SecToCluster[SI];
+
+ SectionIndex BestPred = -1;
+ Double BestWeight = 0;
+
+ for (SectionIndex PI : Sections[SI].Preds) {
+ Edge &E = Edges[EdgeMap[{PI, SI, 0, 0}]];
+ if (BestPred == -1 || E.NormalizedWeight > BestWeight) {
+ BestPred = PI;
+ BestWeight = E.NormalizedWeight;
+ }
+ }
+
+ if (BestWeight < MIN_EDGE_PROBABILITY)
+ 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;
+
+ for (SectionIndex 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() {
+ generateClusters();
+
+ Generate order.
+ llvm::DenseMap<const InputSectionBase *, int> OrderMap;
+ ssize_t CurOrder = 1;
+
+ for (const Cluster &C : Clusters)
+ for (const InputSectionBase *IS : C.ISBs)
+ OrderMap[IS] = 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();
+}

Index: ELF/CMakeLists.txt

• ELF/CMakeLists.txt

+++ ELF/CMakeLists.txt
@@ -19,6 +19,7 @@

Arch/SPARCV9.cpp
Arch/X86.cpp
Arch/X86_64.cpp

+ CallGraphSort.cpp

Driver.cpp
DriverUtils.cpp
EhFrame.cpp

---

llvm-commits mailing list
[e-mail]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

[• rafael]

Michael Spencer via Phabricator via llvm-commits
<[e-mail]> writes:

@@ -1110,6 +1111,14 @@
If no layout was provided by linker script, we want to apply default
sorting for special input sections. This also handles --symbol-ordering-file.
template <class ELFT> void Writer<ELFT>::sortInputSections() {
+ // Use the rarely used option -call-graph-ordering-file to sort sections.
+ if (!Config->CallGraphProfile.empty()) {
+ DenseMap<const InputSectionBase *, int> Order =
+ computeCallGraphProfileOrder();
+ for (BaseCommand *Base : Script->SectionCommands)
+ if (auto *Sec = dyn_cast<OutputSection>(Base))
+ sortSection(Sec, Order);
+ }

Instead of adding this if you can change buildSectionOrder:

static DenseMap<const InputSectionBase *, int> buildSectionOrder() {

if (!Config->CallGraphProfile.empty())
  return computeCallGraphProfileOrder();
...

+ InputSectionBase *FromSec = SymbolSection.lookup(Fields[0]);
+ InputSectionBase *ToSec = SymbolSection.lookup(Fields[1]);
+ if (FromSec && ToSec)
+ Config->CallGraphProfile[std::make_pair(FromSec, ToSec)] = Count;

This should be "+=", no? If there are multiple calls from one section to
another I would expect us to use the total in the graph.

+struct EdgeDenseMapInfo {
+ static Edge getEmptyKey() {
+ return {DenseMapInfo<SectionIndex>::getEmptyKey(),
+ DenseMapInfo<SectionIndex>::getEmptyKey(), 0, 0};
+ }

This doesn't build with clang:

/home/espindola/llvm/llvm/tools/lld/ELF/CallGraphSort.cpp:115:12: error:
no matching constructor for initialization of '(anonymous
namespace)::Edge'

return {DenseMapInfo<SectionIndex>::getEmptyKey(),
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/home/espindola/llvm/llvm/tools/lld/ELF/CallGraphSort.cpp:104:8: note:
candidate constructor (the implicit copy constructor) not viable:
requires 1 argument, but 4 were provided
struct Edge {

^

/home/espindola/llvm/llvm/tools/lld/ELF/CallGraphSort.cpp:104:8: note:
candidate constructor (the implicit move constructor) not viable:
requires 1 argument, but 4 were provided
/home/espindola/llvm/llvm/tools/lld/ELF/CallGraphSort.cpp:104:8: note:
candidate constructor (the implicit default constructor) not viable:
requires 0 arguments, but 4 were provided

Cheers,
Rafael

[• rafael]

Michael Spencer via Phabricator via llvm-commits
<[e-mail]> writes:

+struct Section {
+ Section(const InputSectionBase *IS) : ISB(IS) { Size = ISB->getSize(); }
+
+ Double getDensity() const {
+ if (Size == 0)
+ return 0;
+ return Double(Weight) / Double(Size);
+ }
+
+ int64_t Size = 0;

Why is Size signed? With the previous errors fixed I get a warning:

CallGraphSort.cpp:302:30: warning: comparison of integers of different
signs: 'long' and 'const uint64_t' (aka 'const unsigned long')

Cheers,
Rafael

[• rafael]

I now get this warning:

/home/espindola/llvm/llvm/tools/lld/ELF/CallGraphSort.cpp:204:28:
warning: missing field 'NormalizedWeight' initializer
[-Wmissing-field-initializers]

Edge E{From, To, Weight};

And git-clang-format still produces this diff:

• if (A.getDensity() >
• NewDensity * Double(MAX_DENSITY_DEGRADATION))

+ if (A.getDensity() > NewDensity * Double(MAX_DENSITY_DEGRADATION))

Cheers,
Rafael

Michael Spencer via Phabricator via llvm-commits
<[e-mail]> writes:

Bigcheese updated this revision to Diff 137539.
Bigcheese added a comment.

Address review comments.

https://reviews.llvm.org/D36351

Files:

ELF/CMakeLists.txt
ELF/CallGraphSort.cpp
ELF/CallGraphSort.h
ELF/Config.h
ELF/Driver.cpp
ELF/Options.td
ELF/Writer.cpp
test/ELF/cgprofile-txt.s

Index: test/ELF/cgprofile-txt.s

• /dev/null

+++ test/ELF/cgprofile-txt.s
@@ -0,0 +1,106 @@
+# 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 100" > %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: 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:
+ 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
+
+# CHECK: Name: D
+# CHECK-NEXT: Value: 0x201003
+# 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: 0x201007
+# CHECK: Name: PP
+# CHECK-NEXT: Value: 0x201004
+# CHECK: Name: QC
+# CHECK-NEXT: Value: 0x201006
+# CHECK: Name: TS
+# CHECK-NEXT: Value: 0x201005
+# CHECK: Name: _init
+# CHECK-NEXT: Value: 0x201008
+# CHECK: Name: _init2
+# CHECK-NEXT: Value: 0x201009
+
+# NOSORT: Name: D
+# NOSORT-NEXT: Value: 0x201000
+# 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: 0x201007
+# NOSORT: Name: PP
+# NOSORT-NEXT: Value: 0x201005
+# NOSORT: Name: QC
+# NOSORT-NEXT: Value: 0x201006
+# NOSORT: Name: TS
+# NOSORT-NEXT: Value: 0x201004
+# NOSORT: Name: _init
+# NOSORT-NEXT: Value: 0x201008
+# NOSORT: Name: _init2
+# NOSORT-NEXT: Value: 0x201009

Index: ELF/Writer.cpp

• ELF/Writer.cpp

+++ ELF/Writer.cpp
@@ -9,6 +9,7 @@

#include "Writer.h"
#include "AArch64ErrataFix.h"
+#include "CallGraphSort.h"
#include "Config.h"
#include "Filesystem.h"
#include "LinkerScript.h"
@@ -1020,6 +1021,10 @@
// 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;

Index: ELF/Options.td

• ELF/Options.td

+++ ELF/Options.td
@@ -66,6 +66,9 @@

"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">;

Index: ELF/Driver.cpp

• ELF/Driver.cpp

+++ ELF/Driver.cpp
@@ -571,6 +571,31 @@

return {BuildIdKind::None, {}};

}

+static void readCallGraph(MemoryBufferRef MB) {
+ // Build a map from symbol name to section
+ DenseMap<StringRef, InputSectionBase *> SymbolSection;
+ for (InputFile *File : ObjectFiles)
+ for (Symbol *Sym : File->getSymbols())
+ if (auto *D = dyn_cast<Defined>(Sym))
+ if (auto *IS = dyn_cast_or_null<InputSectionBase>(D->Section))
+ SymbolSection[D->getName()] = IS;
+
+ std::vector<StringRef> Lines = args::getLines(MB);
+ for (StringRef L : Lines) {
+ 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");
+ InputSectionBase *FromSec = SymbolSection.lookup(Fields[0]);
+ InputSectionBase *ToSec = SymbolSection.lookup(Fields[1]);
+ if (FromSec && ToSec)
+ Config->CallGraphProfile[std::make_pair(FromSec, ToSec)] += Count;
+ }
+}
+
static bool getCompressDebugSections(opt::InputArgList &Args) {

StringRef S = Args.getLastArgValue(OPT_compress_debug_sections, "none");
if (S == "none")

@@ -1124,6 +1149,10 @@

// Apply symbol renames for -wrap.
Symtab->applySymbolWrap();

+ if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
+ if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
+ readCallGraph(*Buffer);
+

// Now that we have a complete list of input files.
// Beyond this point, no new files are added.
// Aggregate all input sections into one place.

Index: ELF/Config.h

• ELF/Config.h

+++ ELF/Config.h
@@ -24,6 +24,7 @@
namespace elf {

class InputFile;
+class InputSectionBase;

enum ELFKind {

ELFNoneKind,

@@ -103,6 +104,9 @@

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;

Index: ELF/CallGraphSort.h

• /dev/null

+++ ELF/CallGraphSort.h
@@ -0,0 +1,23 @@
+===- 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

Index: ELF/CallGraphSort.cpp

• /dev/null

+++ ELF/CallGraphSort.cpp
@@ -0,0 +1,350 @@
+===- 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 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"
+
+#include "llvm/Support/MathExtras.h"
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::elf;
+
+namespace {
+using ClusterIndex = std::ptrdiff_t;
+using SectionIndex = std::ptrdiff_t;
+using EdgeIndex = std::ptrdiff_t;
+
+ Used for calculating an comparing density. Use soft-float for determinism.
+struct Double : APFloat {
+ Double() : APFloat(APFloat::IEEEdouble(), 0) {}
+ Double(uint64_t Val) : APFloat(APFloat::IEEEdouble(), Val) {}
+ Double(APFloat A) : APFloat(A) {}
+ bool operator>(const Double Other) const {
+ return compare(Other) == cmpGreaterThan;
+ }
+ bool operator<(const Double Other) const {
+ return compare(Other) == cmpLessThan;
+ }
+};
+
+struct Cluster {
+ Cluster(SectionIndex Sec, const InputSectionBase *IS);
+
+ Double getDensity() const {
+ if (Size == 0)
+ return 0;
+ return Double(Weight) / Double(Size);
+ }
+
+ std::vector<const InputSectionBase *> ISBs;
+ std::vector<SectionIndex> Sections;
+ size_t Size = 0;
+ uint64_t Weight = 0;
+};
+
+struct Section {
+ Section(const InputSectionBase *IS) : ISB(IS) { Size = ISB->getSize(); }
+
+ Double getDensity() const {
+ if (Size == 0)
+ return 0;
+ return Double(Weight) / Double(Size);
+ }
+
+ size_t Size = 0;
+ uint64_t Weight = 0;
+ const InputSectionBase *ISB;
+ std::vector<SectionIndex> Preds;
+ std::vector<SectionIndex> Succs;
+};
+
+struct Edge {
+ SectionIndex From;
+ SectionIndex To;
+ uint64_t Weight;
+ Double NormalizedWeight;
+
+ bool operator==(const Edge Other) const;
+};
+
+struct EdgeDenseMapInfo {
+ static Edge getEmptyKey() {
+ return {DenseMapInfo<SectionIndex>::getEmptyKey(),
+ DenseMapInfo<SectionIndex>::getEmptyKey(), 0, 0};
+ }
+ static Edge getTombstoneKey() {
+ return {DenseMapInfo<SectionIndex>::getTombstoneKey(),
+ DenseMapInfo<SectionIndex>::getTombstoneKey(), 0, 0};
+ }
+ static unsigned getHashValue(const Edge &Val) {
+ return hash_combine(DenseMapInfo<SectionIndex>::getHashValue(Val.From),
+ DenseMapInfo<SectionIndex>::getHashValue(Val.To));
+ }
+ static bool isEqual(const Edge &LHS, const Edge &RHS) { return LHS == RHS; }
+};
+
+class CallGraphSort {
+public:
+ CallGraphSort();
+
+ DenseMap<const InputSectionBase *, int> run();
+
+private:
+ DenseMap<Edge, EdgeIndex, EdgeDenseMapInfo> EdgeMap;
+ std::vector<Cluster> Clusters;
+ std::vector<Edge> Edges;
+ std::vector<Section> Sections;
+
+ void normalizeEdgeWeights();
+ void generateClusters();
+};
+
+ 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
+
+Cluster::Cluster(SectionIndex Sec, const InputSectionBase *IS) {
+ ISBs.push_back(IS);
+ Sections.push_back(Sec);
+ Size = IS->getSize();
+}
+
+bool Edge::operator==(const Edge Other) const {
+ return From == Other.From && To == Other.To;
+}
+
+ Take the edge list in Config->CallGraphProfile, resolve symbol names to
+ Symbols, and generate a graph between InputSections with the provided
+ weights.
+CallGraphSort::CallGraphSort() {
+ MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
+ uint64_t> &Profile = Config->CallGraphProfile;
+ DenseMap<const InputSectionBase *, SectionIndex> SecToSec;
+
+ auto GetOrCreateNode = [&](const InputSectionBase *IS) -> SectionIndex {
+ auto Res = SecToSec.insert(std::make_pair(IS, Sections.size()));
+ if (Res.second)
+ Sections.emplace_back(IS);
+ return Res.first->second;
+ };
+
+ Create the graph.
+ for (const auto &C : Profile) {
+ const InputSectionBase *FromSB = C.first.first;
+ const InputSectionBase *ToSB = C.first.second;
+ uint64_t Weight = C.second;
+
+ if (Weight == 0)
+ continue;
+
+ 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;
+
+ SectionIndex From = GetOrCreateNode(FromSB);
+ SectionIndex To = GetOrCreateNode(ToSB);
+
+ Sections[To].Weight = SaturatingAdd(Sections[To].Weight, Weight);
+
+ if (From == To)
+ continue;
+
+ Edge E{From, To, Weight};
+
+ Add or increment an edge
+ auto Res = EdgeMap.insert(std::make_pair(E, Edges.size()));
+ EdgeIndex EI = Res.first->second;
+ if (Res.second) {
+ Edges.push_back(E);
+ Sections[From].Succs.push_back(To);
+ Sections[To].Preds.push_back(From);
+ } else
+ Edges[EI].Weight = SaturatingAdd(Edges[EI].Weight, Weight);
+ }
+ normalizeEdgeWeights();
+}
+
+ Normalize the edge weights so that we can reject edges which have a low
+ probibility.
+void CallGraphSort::normalizeEdgeWeights() {
+ for (SectionIndex SI = 0, SE = Sections.size(); SI != SE; ++SI) {
+ Section &S = Sections[SI];
+ for (SectionIndex PI : S.Preds) {
+ Edge &E = Edges[EdgeMap[{PI, SI, 0, 0}]];
+ if (S.Weight == 0)
+ continue;
+ E.NormalizedWeight = Double(E.Weight) / Double(S.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 (A.getDensity() >
+ NewDensity * Double(MAX_DENSITY_DEGRADATION))
+ return true;
+ return false;
+}
+
+static void mergeClusters(Cluster &Into, Cluster &From) {
+ Into.ISBs.insert(Into.ISBs.end(), From.ISBs.begin(), From.ISBs.end());
+ Into.Sections.insert(Into.Sections.end(), From.Sections.begin(),
+ From.Sections.end());
+ Into.Size += From.Size;
+ Into.Weight += From.Weight;
+ From.ISBs.clear();
+ 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::generateClusters() {
+ Minimum edge probability to consider merging.
+ const Double MIN_EDGE_PROBABILITY = Double(1) / Double(10);
+
+ std::vector<SectionIndex> SortedSecs;
+ std::vector<Cluster *> SecToCluster(Sections.size());
+
+ Clusters.reserve(Sections.size());
+
+ for (SectionIndex SI = 0, SE = Sections.size(); SI != SE; ++SI) {
+ Cluster C(SI, Sections[SI].ISB);
+ C.Size = Sections[SI].Size;
+ C.Weight = Sections[SI].Weight;
+ Clusters.push_back(C);
+ SortedSecs.push_back(SI);
+ }
+
+ for (Cluster &C : Clusters) {
+ SecToCluster[C.Sections.front()] = &C;
+ }
+
+ std::stable_sort(SortedSecs.begin(), SortedSecs.end(),
+ [&](SectionIndex A, SectionIndex B) {
+ return Sections[A].getDensity() > Sections[B].getDensity();
+ });
+
+ for (SectionIndex SI : SortedSecs) {
+ Cluster &C = *SecToCluster[SI];
+
+ SectionIndex BestPred = -1;
+ Double BestWeight = 0;
+
+ for (SectionIndex PI : Sections[SI].Preds) {
+ Edge &E = Edges[EdgeMap[{PI, SI, 0, 0}]];
+ if (BestPred == -1 || E.NormalizedWeight > BestWeight) {
+ BestPred = PI;
+ BestWeight = E.NormalizedWeight;
+ }
+ }
+
+ if (BestWeight < MIN_EDGE_PROBABILITY)
+ 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;
+
+ for (SectionIndex 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() {
+ generateClusters();
+
+ Generate order.
+ llvm::DenseMap<const InputSectionBase *, int> OrderMap;
+ ssize_t CurOrder = 1;
+
+ for (const Cluster &C : Clusters)
+ for (const InputSectionBase *IS : C.ISBs)
+ OrderMap[IS] = 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();
+}

Index: ELF/CMakeLists.txt

• ELF/CMakeLists.txt

+++ ELF/CMakeLists.txt
@@ -19,6 +19,7 @@

Arch/SPARCV9.cpp
Arch/X86.cpp
Arch/X86_64.cpp

+ CallGraphSort.cpp

Driver.cpp
DriverUtils.cpp
EhFrame.cpp

---

llvm-commits mailing list
[e-mail]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

[• rafael]

+static void readCallGraph(MemoryBufferRef MB) {
+ // Build a map from symbol name to section
+ DenseMap<StringRef, InputSectionBase *> SymbolSection;
+ for (InputFile *File : ObjectFiles)
+ for (Symbol *Sym : File->getSymbols())
+ if (auto *D = dyn_cast<Defined>(Sym))
+ if (auto *IS = dyn_cast_or_null<InputSectionBase>(D->Section))
+ SymbolSection[D->getName()] = IS;
+
+ std::vector<StringRef> Lines = args::getLines(MB);
+ for (StringRef L : Lines) {
+ 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");
+ InputSectionBase *FromSec = SymbolSection.lookup(Fields[0]);
+ InputSectionBase *ToSec = SymbolSection.lookup(Fields[1]);
+ if (FromSec && ToSec)
+ Config->CallGraphProfile[std::make_pair(FromSec, ToSec)] += Count;

Should this be using FromSec->Repl, ToSec->Repl to handle ICF? If so
please update the code and add a new test (the one in the patch is
getting big).

+ }
+}

With --symbol-ordering-file we produce warnings if, for example, the
symbol is found to be absolute. The same issue applies here, no? Can you
refactor the code so that we print the same warnings for
--call-graph-ordering-file?

+using ClusterIndex = std::ptrdiff_t;
+using SectionIndex = std::ptrdiff_t;
+using EdgeIndex = std::ptrdiff_t;

Does this means that we use 64 bit integers for indexes? Why?

+// Used for calculating an comparing density. Use soft-float for determinism.
+struct Double : APFloat {

This used to be a problem with x87, but do we support a system today
where this is a problem?

Cheers,
Rafael

[Bigcheese]

Apply review comments.

After discussing the floating point issue with people and checking compilers, I believe this specific use is safe as there is no opportunity to form FMAs and it only uses division and comparison.

[• espindola]

ELF/CallGraphSort.cpp

246 ↗

(On Diff #139535)

please git-clang-format the patch.

[• espindola]

ELF/CallGraphSort.cpp

158 ↗

(On Diff #139535)

This warning is duplicated with what we have in Writer.cpp for --symbol-ordering-file. Could it be merged?

277 ↗

(On Diff #139535)

Delete extra empty lines.

[Bigcheese]

Address review comments.

[• espindola]

ELF/CallGraphSort.cpp

56 ↗

(On Diff #140132)

dead code.

57 ↗

(On Diff #140132)

Why do you need a 64 bit index. Why does it need a typedef?

[• espindola]

ELF/CallGraphSort.cpp

149 ↗

(On Diff #140132)

const Edge &Other

ELF/Config.h

27 ↗

(On Diff #140132)

dead declaration.

ELF/Driver.cpp

600 ↗

(On Diff #140132)

This should now be just =, no?

[Bigcheese]

ELF/CallGraphSort.cpp

57 ↗

(On Diff #140132)

While ELF limits the number of sections/symbols a single ELF file can hold, there's no limit on the number of input sections that go into the final link. If we have multiple ELF files with 4bn sections, then this could overflow. The chances of this are rare, but there's almost no cost in supporting it. The correct default type for array indexing is std::ptrdiff_t, you need a good reason to use something else.

As for the typedef, it makes it clearer what the purpose of the index is. Otherwise they would all have the same type. If C++ had a good way to do strong typedefs I would be using that here to add compile time enforcement.

ELF/Driver.cpp

600 ↗

(On Diff #140132)

It should be a saturating add. An input file can legitimately have multiple edges, and they should be merged.

[Bigcheese]

Address review comments.

[• espindola]

ELF/CallGraphSort.cpp

57 ↗

(On Diff #140132)

The reason is that nothing in lld does this.

Just use int/unsigned as appropriate. We do not design for an abstract pie in the sky.

Change this.

[Bigcheese]

Address review comments.

[• espindola]

ELF/CallGraphSort.cpp

56 ↗

(On Diff #140713)

Delete these typedefs and just use the proper type directly.

148 ↗

(On Diff #140713)

Define this inline.

ELF/Driver.cpp

602 ↗

(On Diff #140713)

This means that we supports having duplicated symbol edges. Is there a reason for that? If not please change this to report an error on duplicated edges.

[• espindola]

ELF/CallGraphSort.cpp

201 ↗

(On Diff #140713)

This is using SaturatingAdd on a uint64_t. That also seems like over engineering.

Each unit of edge weight comes from a sample during execution. Even with a compact format using a single byte per sample we would need 16 exbibytes for it to overflow. Where would such a sample have been stored?

[• espindola]

ELF/CallGraphSort.cpp

148 ↗

(On Diff #140713)

Actually, it is only called once. Inline it.

[• espindola]

ELF/Driver.cpp

611–612 ↗

(On Diff #110323)

This is marked done, but it is not.

[Bigcheese]

ELF/CallGraphSort.cpp

56 ↗

(On Diff #140713)

That would significantly reduce code clarity. It's not uncommon in LLVM to do this. LLD even has a case of this with Relocations.h RelType.

ELF/Driver.cpp

602 ↗

(On Diff #140713)

This makes it easier to create input. For instance you can cat together profiles from different runs.

[Bigcheese]

Address review comments.

[• espindola]

ELF/CallGraphSort.cpp

56 ↗

(On Diff #140713)

RelType is the one example in lld and its use spans most of the linker, so it makes sense there. This is completely local and is just noise. Delete it.

ELF/Symbols.cpp

251 ↗

(On Diff #141236)

Rebase on top of r329371. You should be able to remove the File argument with that.

[• espindola]

ELF/CallGraphSort.cpp

49 ↗

(On Diff #141236)

Dead include.

ELF/Driver.cpp

602 ↗

(On Diff #140713)

Fair enough. Please add a testcase showing that behavior.

[Bigcheese]

Address review comments.

[• espindola]

ELF/CallGraphSort.cpp

32 ↗

(On Diff #141718)

The part about profile should be in a followup patch. For now this is given the weighted call graph.

63 ↗

(On Diff #141718)

You can remove this vector.

The only real use is when computing the returned DenseMap and you can use the Sections vector there:

for (const Cluster &C : Clusters)
  for (int SecIndex : C.Sections)
    OrderMap[Sections[SecIndex].ISB] = CurOrder++;

137 ↗

(On Diff #141718)

Define this function inline.

263 ↗

(On Diff #141718)

You don't need this loop, just add

SecToCluster[SI] = &Clusters.back();

to the previous one.

297 ↗

(On Diff #141718)

This is a slow union find solution when there are many union operations. Maybe that doesn't impact this in practice, but at least leave a comment about a possible improvement if we ever hit it.

[Bigcheese]

Address review comments.

ELF/CallGraphSort.cpp

32 ↗

(On Diff #141718)

This is talking about the for loop in CallGraphSort() where it builds the graph.

[• espindola]

ELF/CallGraphSort.cpp

203 ↗

(On Diff #142093)

This is not tested. All tests pass if I replace it with an assert.

32 ↗

(On Diff #141718)

Building a graph from a set of edges doesn't sound much, but it is OK to keep the comment. Just don't use the word profile as it makes it sound like lld is reading the direct output of perf or similar.

[• espindola]

test/ELF/cgprofile-txt.s

8 ↗

(On Diff #142093)

This should be >>, no?

[• espindola]

ELF/CallGraphSort.cpp

71 ↗

(On Diff #142093)

This structure is almost a perfect duplicate of Cluster. That is not too surprising since each cluster starts as a single section.

In the traditional description of union-find, there is only one type of element which gets combined as union operations are performed.

I was able to remove this struct and I think it makes the code quite a bite closer to a description of the union-find structure and easier to read. The patch on top of this is at https://reviews.llvm.org/D45577.

289 ↗

(On Diff #142093)

BTW, this is a very interesting problem.

The traditional disjoint-set/union-find uses unordered sets which are easy to represent with trees with only parent pointers.

Changing it to represent order in the sets and still be efficient is an interesting challenge (not for this patch).

[Bigcheese]

Addressed review comments.

[Bigcheese]

ELF/CallGraphSort.cpp

32 ↗

(On Diff #141718)

I've made it clear it's talking about the call graph profile, not whatever profile that was generated from.

[• espindola]

ELF/CallGraphSort.cpp

198 ↗

(On Diff #142272)

Instead of storing a normalized edge value it is simpler to store the original cluster weight: https://reviews.llvm.org/D45607

257 ↗

(On Diff #142272)

This is not tested.

This is not in the paper, right? Do you know what is the motivation? It is interesting in that the algorithm prioritizes hot nodes, but has a limit on how cold an edge can be.

It does seem to have a small performance win, at lest on the LTOing FileCheck testcase. With this patch a run takes 2.519023951 seconds, with this check removed it takes 2.520792327 (no sorting is 2.575764375).

[• espindola]

ELF/CallGraphSort.cpp

70 ↗

(On Diff #142272)

Succs is not used, please delete.

[• espindola]

ELF/Config.h

108 ↗

(On Diff #142272)

Using Symbol in here causes some duplication. We support duplicated edges, and we have to support two symbols pointing to the same section. This means two maps, this one for symbols and one for edges from section to section.

If this map is changed to directly map from section to section, we can avoid the second map completely:

https://reviews.llvm.org/D45630

[Bigcheese]

Address review comments.

[• espindola]

LGTM with a few last requests.

ELF/CallGraphSort.cpp

180 ↗

(On Diff #142708)

Since this is looking at a section we haven't merged to a predecessor yet this can be just

Cluster &C = Clusters[SI];

185 ↗

(On Diff #142708)

This can be just C.Preds.

192 ↗

(On Diff #142708)

You don't think you need this if. If there are no predecessors, BestWeight will be 0 and so the following if will continue since InitialWeight is unsigned.

206 ↗

(On Diff #142708)

All tests pass if I delete this if. Please add a test.

212 ↗

(On Diff #142708)

All tests pass if I delete this loop. Please add a test.

224 ↗

(On Diff #142708)

NodeIndex is not used elsewhere in the patch. What this (and the previous remove_if) invalidate are the cluster to cluster edges.

lld/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

lld/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();
+}
+}
+
+#endif

lld/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.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file This file implements 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 weight edge
+///     from cluster _u_ to _v_ then move the sections in _v_ and append them to
+///     _u_ unless the combined size would be larger than the page size.
+/// * 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 call graph from the profile
+/// * While there are unresolved edges
+///   * Find the edge with the highest weight
+///   * Check if merging the two clusters would create a cluster larger than the
+///     target page size
+///   * If not, contract that edge putting the callee after the caller
+/// * Sort remaining clusters by density
+///
+//===----------------------------------------------------------------------===//
+
+#include "CallGraphSort.h"
+#include "SymbolTable.h"
+#include "Target.h"
+
+#include "llvm/Support/MathExtras.h"
+
+#include <queue>
+#include <set>
+#include <unordered_map>
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::elf;
+
+namespace {
+class CallGraphSort {
+  using NodeIndex = std::ptrdiff_t;
+  using EdgeIndex = std::ptrdiff_t;
+
+  struct Node {
+    Node() = default;
+    Node(const InputSectionBase *IS);
+    std::vector<const InputSectionBase *> Sections;
+    std::vector<EdgeIndex> IncidentEdges;
+    int64_t Size = 0;
+    uint64_t Weight = 0;
+  };
+
+  struct Edge {
+    NodeIndex From;
+    NodeIndex To;
+    mutable uint64_t Weight;
+    bool operator==(const Edge Other) const;
+    bool operator<(const Edge Other) const;
+    void kill();
+    bool isDead() const;
+  };
+
+  struct EdgeDenseMapInfo {
+    static Edge getEmptyKey() {
+      return {DenseMapInfo<NodeIndex>::getEmptyKey(),
+              DenseMapInfo<NodeIndex>::getEmptyKey(), 0};
+    }
+    static Edge getTombstoneKey() {
+      return {DenseMapInfo<NodeIndex>::getTombstoneKey(),
+              DenseMapInfo<NodeIndex>::getTombstoneKey(), 0};
+    }
+    static unsigned getHashValue(const Edge &Val) {
+      return hash_combine(DenseMapInfo<NodeIndex>::getHashValue(Val.From),
+                          DenseMapInfo<NodeIndex>::getHashValue(Val.To));
+    }
+    static bool isEqual(const Edge &LHS, const Edge &RHS) { return LHS == RHS; }
+  };
+
+  std::vector<Node> Nodes;
+  std::vector<Edge> Edges;
+  struct EdgePriorityCmp {
+    std::vector<Edge> &Edges;
+    bool operator()(EdgeIndex A, EdgeIndex B) const {
+      return Edges[A].Weight < Edges[B].Weight;
+    }
+  };
+
+  typedef std::multiset<EdgeIndex, EdgePriorityCmp> priority;
+  typedef std::unordered_map<EdgeIndex, priority::const_iterator> priority_lookup;
+
+  priority WorkQueue{EdgePriorityCmp{Edges}};
+  priority_lookup WorkLookup;
+
+  void contractEdge(EdgeIndex CEI);
+  void generateClusters();
+
+public:
+  CallGraphSort(DenseMap<std::pair<const Symbol *, const Symbol *>,
+                         uint64_t> &Profile);
+
+  DenseMap<const InputSectionBase *, int> run();
+};
+} // end anonymous namespace
+
+CallGraphSort::Node::Node(const InputSectionBase *IS) {
+  Sections.push_back(IS);
+  Size = IS->getSize();
+}
+
+bool CallGraphSort::Edge::operator==(const Edge Other) const {
+  return From == Other.From && To == Other.To;
+}
+
+bool CallGraphSort::Edge::operator<(const Edge Other) const {
+  if (From != Other.From)
+    return From < Other.From;
+  return To < Other.To;
+}
+
+void CallGraphSort::Edge::kill() {
+  From = 0;
+  To = 0;
+}
+
+bool CallGraphSort::Edge::isDead() const { return From == 0 && To == 0; }
+
+// Take the edge list in Config->CallGraphProfile, resolve symbol names to
+// Symbols, and generate a graph between InputSections with the provided
+// weights.
+CallGraphSort::CallGraphSort(
+    DenseMap<std::pair<const Symbol *, const Symbol *>, uint64_t>
+        &Profile) {
+  DenseMap<const InputSectionBase *, NodeIndex> SecToNode;
+  DenseMap<Edge, EdgeIndex, EdgeDenseMapInfo> EdgeMap;
+
+  auto GetOrCreateNode = [&](const InputSectionBase *IS) -> NodeIndex {
+    auto Res = SecToNode.insert(std::make_pair(IS, Nodes.size()));
+    if (Res.second)
+      Nodes.emplace_back(IS);
+    return Res.first->second;
+  };
+
+  // Create the graph.
+  for (const auto &C : Profile) {
+    const Symbol *FromSym = C.first.first;
+    const Symbol *ToSym = C.first.second;
+    uint64_t Weight = C.second;
+
+    if (Weight == 0)
+      continue;
+
+    // Get the input section for a given symbol.
+    auto *FromDR = dyn_cast_or_null<Defined>(FromSym);
+    auto *ToDR = dyn_cast_or_null<Defined>(ToSym);
+    if (!FromDR || !ToDR)
+      continue;
+
+    auto *FromSB = dyn_cast_or_null<const InputSectionBase>(FromDR->Section);
+    auto *ToSB = dyn_cast_or_null<const InputSectionBase>(ToDR->Section);
+    if (!FromSB || !ToSB || FromSB->getSize() == 0 || ToSB->getSize() == 0)
+      continue;
+
+    NodeIndex From = GetOrCreateNode(FromSB);
+    NodeIndex To = GetOrCreateNode(ToSB);
+    Edge E{From, To, Weight};
+
+    // Add or increment an edge
+    auto Res = EdgeMap.insert(std::make_pair(E, Edges.size()));
+    EdgeIndex EI = Res.first->second;
+    if (Res.second) {
+      Edges.push_back(E);
+      Nodes[From].IncidentEdges.push_back(EI);
+      Nodes[To].IncidentEdges.push_back(EI);
+    } else
+      Edges[EI].Weight = SaturatingAdd(Edges[EI].Weight, Weight);
+
+    Nodes[To].Weight = SaturatingAdd(Nodes[To].Weight, Weight);
+  }
+}
+
+/// Remove edge \p CEI from the graph while simultaneously merging its two
+/// incident vertices u and v. This merges any duplicate edges between u and v
+/// by accumulating their weights.
+void CallGraphSort::contractEdge(EdgeIndex CEI) {
+  // Make a copy of the edge as the original will be marked killed while being
+  // used.
+  Edge CE = Edges[CEI];
+  if (CE.From == CE.To) {
+    auto I = WorkLookup.find(CEI);
+    if (I != WorkLookup.end()) {
+      WorkQueue.erase(I->second);
+      WorkLookup.erase(I);
+    } else
+      assert(std::find(WorkQueue.begin(), WorkQueue.end(), CEI) ==
+             WorkQueue.end());
+    Edges[CEI].kill();
+    return;
+  }
+  std::vector<EdgeIndex> &FE = Nodes[CE.From].IncidentEdges;
+
+  // Remove the self edge from From.
+  FE.erase(std::remove(FE.begin(), FE.end(), CEI));
+  std::vector<EdgeIndex> &TE = Nodes[CE.To].IncidentEdges;
+
+  // Update all edges incident with To to reference From instead. Then if they
+  // aren't self edges add them to From.
+  for (EdgeIndex EI : TE) {
+    Edge &E = Edges[EI];
+    if (E.From == CE.To)
+      E.From = CE.From;
+    if (E.To == CE.To)
+      E.To = CE.From;
+    if (E.To == E.From) {
+      E.kill();
+      continue;
+    }
+    FE.push_back(EI);
+  }
+
+  // Free memory.
+  std::vector<EdgeIndex>().swap(TE);
+
+  if (FE.empty())
+    return;
+
+  // Sort edges so they can be merged. The stability of this sort doesn't matter
+  // as equal edges will be merged in an order independent manner.
+  std::sort(FE.begin(), FE.end(),
+            [&](EdgeIndex AI, EdgeIndex BI) { return Edges[AI] < Edges[BI]; });
+
+  // std::unique, but also merge equal values.
+  auto First = FE.begin();
+  auto Last = FE.end();
+  auto Result = First;
+  while (++First != Last) {
+    if (Edges[*Result] == Edges[*First]) {
+      // Remove first and result.
+      auto F = WorkLookup.find(*First);
+      if (F != WorkLookup.end()) {
+        WorkQueue.erase(F->second);
+        WorkLookup.erase(F);
+      } else
+        assert(std::find(WorkQueue.begin(), WorkQueue.end(), *First) ==
+               WorkQueue.end());
+      auto R = WorkLookup.find(*Result);
+      if (R == WorkLookup.end()) {
+        assert(std::find(WorkQueue.begin(), WorkQueue.end(), *Result) ==
+               WorkQueue.end());
+        R = WorkLookup.insert(std::make_pair(*Result, WorkQueue.end())).first;
+      } else
+        WorkQueue.erase(R->second);
+
+      Edges[*Result].Weight =
+          SaturatingAdd(Edges[*Result].Weight, Edges[*First].Weight);
+      Edges[*First].kill();
+
+      // Reinsert result.
+      R->second = WorkQueue.insert(*Result);
+    } else if (++Result != First)
+      *Result = *First;
+  }
+  FE.erase(++Result, FE.end());
+}
+
+// Group InputSections into clusters using the Call-Chain Clustering heuristic
+// then sort the clusters by density.
+void CallGraphSort::generateClusters() {
+  for (size_t I = 0; I < Edges.size(); ++I) {
+    WorkLookup[I] = WorkQueue.insert(I);
+  }
+
+  // Collapse the graph.
+  while (!WorkQueue.empty()) {
+    priority::const_iterator I = --WorkQueue.end();
+    EdgeIndex MaxI = *I;
+    const Edge MaxE = Edges[MaxI];
+    WorkLookup.erase(*I);
+    WorkQueue.erase(I);
+    if (MaxE.isDead())
+      continue;
+    // Merge the Nodes.
+    Node &From = Nodes[MaxE.From];
+    Node &To = Nodes[MaxE.To];
+    if (From.Size + To.Size > Target->PageSize)
+      continue;
+    contractEdge(MaxI);
+    From.Sections.insert(From.Sections.end(), To.Sections.begin(),
+                         To.Sections.end());
+    From.Size += To.Size;
+    From.Weight = SaturatingAdd(From.Weight, To.Weight);
+    To.Sections.clear();
+    To.Size = 0;
+    To.Weight = 0;
+  }
+
+  // Remove empty or dead nodes.
+  Nodes.erase(std::remove_if(Nodes.begin(), Nodes.end(),
+                             [](const Node &N) {
+                               return N.Size == 0 || N.Sections.empty();
+                             }),
+              Nodes.end());
+
+  // Sort by density. Invalidates all NodeIndexs.
+  std::sort(Nodes.begin(), Nodes.end(), [](const Node &A, const Node &B) {
+    return (APFloat(APFloat::IEEEdouble(), A.Weight) /
+            APFloat(APFloat::IEEEdouble(), A.Size))
+               .compare(APFloat(APFloat::IEEEdouble(), B.Weight) /
+                        APFloat(APFloat::IEEEdouble(), B.Size)) ==
+           APFloat::cmpLessThan;
+  });
+}
+
+DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
+  generateClusters();
+
+  // Generate order.
+  llvm::DenseMap<const InputSectionBase *, int> OrderMap;
+  ssize_t CurOrder = 1;
+
+  for (const Node &N : Nodes)
+    for (const InputSectionBase *IS : N.Sections)
+      OrderMap[IS] = 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 iteratively
+// merges the hottest call edges as long as it would not create a cluster larger
+// than the page size. All clusters are then sorted by a density metric to
+// further improve locality.
+DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
+  return CallGraphSort(Config->CallGraphProfile).run();
+}

lld/ELF/Config.h

 //===- Config.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_CONFIG_H
 #define LLD_ELF_CONFIG_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/Endian.h"
 
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class InputFile;
+class Symbol;
 
 enum ELFKind {
   ELFNoneKind,
   ELF32LEKind,
   ELF32BEKind,
   ELF64LEKind,
   ELF64BEKind
 };
struct Configuration {
   llvm::StringRef LTOAAPipeline;
   llvm::StringRef LTONewPmPasses;
   llvm::StringRef MapFile;
   llvm::StringRef OutputFile;
   llvm::StringRef OptRemarksFilename;
   llvm::StringRef SoName;
   llvm::StringRef Sysroot;
   llvm::StringRef ThinLTOCacheDir;
+  llvm::StringRef CallGraphProfileFile;
   std::string Rpath;
   std::vector<VersionDefinition> VersionDefinitions;
   std::vector<llvm::StringRef> Argv;
   std::vector<llvm::StringRef> AuxiliaryList;
   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::DenseMap<std::pair<const Symbol *, const Symbol *>, uint64_t>
+      CallGraphProfile;
   bool AllowMultipleDefinition;
   bool AndroidPackDynRelocs = false;
   bool ARMHasBlx = false;
   bool ARMHasMovtMovw = false;
   bool ARMJ1J2BranchEncoding = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
+  bool CallGraphProfileSort = true;
   bool CompressDebugSections;
   bool DefineCommon;
   bool Demangle = true;
   bool DisableVerify;
   bool EhFrameHdr;
   bool EmitRelocs;
   bool EnableNewDtags;
   bool ExportDynamic;

lld/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, {}};
 }
 
+// This reads a list of call edges with weights one line at a time from a file
+// with the following format for each line:
+//
+// ^[.*]+ [.*]+ [.*]+$
+//
+// It interprets the first value as an unsigned 64 bit weight, the second as
+// the symbol the call is from, and the third as the symbol the call is to.
+//
+// Example:
+//
+// 5000 c a
+// 4000 c b
+// 18446744073709551615 e d
+//
+template <typename ELFT>
+void readCallGraphProfile(MemoryBufferRef MB) {
+  for (StringRef L : args::getLines(MB)) {
+    SmallVector<StringRef, 3> Fields;
+    L.split(Fields, ' ');
+    if (Fields.size() != 3) {
+      error("parse error: " + MB.getBufferIdentifier() + ": " + L);
+      return;
+    }
+    uint64_t Count;
+    if (!to_integer(Fields[0], Count)) {
+      error("parse error: " + MB.getBufferIdentifier() + ": " + L);
+      return;
+    }
+    StringRef From = Fields[1];
+    StringRef To = Fields[2];
+    Config->CallGraphProfile[std::make_pair(Symtab->addUndefined<ELFT>(From),
+                                            Symtab->addUndefined<ELFT>(To))] =
+        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");

 
 // Initializes Config members by the command line options.
 void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->AllowMultipleDefinition =
       Args.hasArg(OPT_allow_multiple_definition) || hasZOption(Args, "muldefs");
   Config->AuxiliaryList = args::getStrings(Args, OPT_auxiliary);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
+  Config->CallGraphProfileSort = Args.hasFlag(
+      OPT_call_graph_profile_sort, OPT_no_call_graph_profile_sort, true);
   Config->Chroot = Args.getLastArgValue(OPT_chroot);
   Config->CompressDebugSections = getCompressDebugSections(Args);
   Config->DefineCommon = Args.hasFlag(OPT_define_common, OPT_no_define_common,
                                       !Args.hasArg(OPT_relocatable));
   Config->Demangle = Args.hasFlag(OPT_demangle, OPT_no_demangle, true);
   Config->DisableVerify = Args.hasArg(OPT_disable_verify);
   Config->Discard = getDiscard(Args);
   Config->DynamicLinker = getDynamicLinker(Args);
if (auto *Arg = Args.getLastArg(OPT_pack_dyn_relocs_eq)) {
     else if (S != "none")
       error("unknown -pack-dyn-relocs format: " + S);
   }
 
   if (auto *Arg = Args.getLastArg(OPT_symbol_ordering_file))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       Config->SymbolOrderingFile = args::getLines(*Buffer);
 
+  if (auto *Arg = Args.getLastArg(OPT_call_graph_profile_file))
+    Config->CallGraphProfileFile = Arg->getValue();
+
   // If --retain-symbol-file is used, we'll keep only the symbols listed in
   // the file and discard all others.
   if (auto *Arg = Args.getLastArg(OPT_retain_symbols_file)) {
     Config->DefaultSymbolVersion = VER_NDX_LOCAL;
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       for (StringRef S : args::getLines(*Buffer))
         Config->VersionScriptGlobals.push_back(
             {S, /*IsExternCpp*/ false, /*HasWildcard*/ false});
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // dynamic symbol table.
   // We need one if we were asked to export dynamic symbols or if we are
   // producing a shared library.
   // We also need one if any shared libraries are used and for pie executables
   // (probably because the dynamic linker needs it).
   Config->HasDynSymTab =
       !SharedFiles.empty() || Config->Pic || Config->ExportDynamic;
 
+  if (!Config->CallGraphProfileFile.empty())
+    if (Optional<MemoryBufferRef> Buffer =
+            readFile(Config->CallGraphProfileFile))
+      readCallGraphProfile<ELFT>(*Buffer);
+
   // Some symbols (such as __ehdr_start) are defined lazily only when there
   // are undefined symbols for them, so we add these to trigger that logic.
   for (StringRef Sym : Script->ReferencedSymbols)
     Symtab->addUndefined<ELFT>(Sym);
 
   // Handle the `--undefined <sym>` options.
   for (StringRef S : Config->Undefined)
     Symtab->fetchIfLazy<ELFT>(S);

lld/ELF/InputFiles.h

 // .o file.
 template <class ELFT> class ObjFile : public ELFFileBase<ELFT> {
   typedef ELFFileBase<ELFT> Base;
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Word Elf_Word;
+  typedef typename ELFT::CGProfile Elf_CGProfile;
 
   StringRef getShtGroupSignature(ArrayRef<Elf_Shdr> Sections,
                                  const Elf_Shdr &Sec);
   ArrayRef<Elf_Word> getShtGroupEntries(const Elf_Shdr &Sec);
 
 public:
   static bool classof(const InputFile *F) { return F->kind() == Base::ObjKind; }
 
public:
   // symbol table.
   StringRef SourceFile;
 
 private:
   void
   initializeSections(llvm::DenseSet<llvm::CachedHashStringRef> &ComdatGroups);
   void initializeSymbols();
   void initializeDwarf();
+  void parseCGProfile();
   InputSectionBase *getRelocTarget(const Elf_Shdr &Sec);
   InputSectionBase *createInputSection(const Elf_Shdr &Sec);
   StringRef getSectionName(const Elf_Shdr &Sec);
 
   bool shouldMerge(const Elf_Shdr &Sec);
   Symbol *createSymbol(const Elf_Sym *Sym);
 
   // .shstrtab contents.
   StringRef SectionStringTable;
 
   // Debugging information to retrieve source file and line for error
   // reporting. Linker may find reasonable number of errors in a
   // single object file, so we cache debugging information in order to
   // parse it only once for each object file we link.
   std::unique_ptr<llvm::DWARFDebugLine> DwarfLine;
   llvm::DenseMap<StringRef, std::pair<unsigned, unsigned>> VariableLoc;
   llvm::once_flag InitDwarfLine;
+
+  ArrayRef<Elf_CGProfile> CGProfile;
 };
 
 // LazyObjFile is analogous to ArchiveFile in the sense that
 // the file contains lazy symbols. The difference is that
 // LazyObjFile wraps a single file instead of multiple files.
 //
 // This class is used for --start-lib and --end-lib options which
 // instruct the linker to link object files between them with the

lld/ELF/InputFiles.cpp

 // using DWARF debug info.
 template <class ELFT>
 std::string ObjFile<ELFT>::getLineInfo(InputSectionBase *S, uint64_t Offset) {
   if (Optional<DILineInfo> Info = getDILineInfo(S, Offset))
     return Info->FileName + ":" + std::to_string(Info->Line);
   return "";
 }
 
+template<class ELFT>
+void lld::elf::ObjFile<ELFT>::parseCGProfile() {
+  for (const Elf_CGProfile &CGPE : CGProfile) {
+    uint64_t &C = Config->CallGraphProfile[std::make_pair(
+        &getSymbol(CGPE.cgp_from), &getSymbol(CGPE.cgp_to))];
+    C = std::max(C, (uint64_t)CGPE.cgp_weight);
+  }
+}
+
 // Returns "<internal>", "foo.a(bar.o)" or "baz.o".
 std::string lld::toString(const InputFile *F) {
   if (!F)
     return "<internal>";
 
   if (F->ToStringCache.empty()) {
     if (F->ArchiveName.empty())
       F->ToStringCache = F->getName();
template <class ELFT> ArrayRef<Symbol *> ObjFile<ELFT>::getLocalSymbols() {
   return makeArrayRef(this->Symbols).slice(1, this->FirstNonLocal - 1);
 }
 
 template <class ELFT>
 void ObjFile<ELFT>::parse(DenseSet<CachedHashStringRef> &ComdatGroups) {
   // Read section and symbol tables.
   initializeSections(ComdatGroups);
   initializeSymbols();
+  parseCGProfile();
 }
 
 // Sections with SHT_GROUP and comdat bits define comdat section groups.
 // They are identified and deduplicated by group name. This function
 // returns a group name.
 template <class ELFT>
 StringRef ObjFile<ELFT>::getShtGroupSignature(ArrayRef<Elf_Shdr> Sections,
                                               const Elf_Shdr &Sec) {
if (Name.startswith(".gnu.linkonce."))
     return &InputSection::Discarded;
 
   // The linker merges EH (exception handling) frames and creates a
   // .eh_frame_hdr section for runtime. So we handle them with a special
   // class. For relocatable outputs, they are just passed through.
   if (Name == ".eh_frame" && !Config->Relocatable)
     return make<EhInputSection>(this, &Sec, Name);
 
+  // Profile data.
+  if (Name == ".note.llvm.cgprofile") {
+    CGProfile = check(
+        this->getObj().template getSectionContentsAsArray<Elf_CGProfile>(&Sec));
+    return &InputSection::Discarded;
+  }
+
   if (shouldMerge(Sec))
     return make<MergeInputSection>(this, &Sec, Name);
   return make<InputSection>(this, &Sec, Name);
 }
 
 template <class ELFT>
 StringRef ObjFile<ELFT>::getSectionName(const Elf_Shdr &Sec) {
   return check(this->getObj().getSectionName(&Sec, SectionStringTable),

lld/ELF/Options.td

defm Ttext: Eq<"Ttext">,
   HelpText<"Same as --section-start with .text as the sectionname">;
 
 def allow_multiple_definition: F<"allow-multiple-definition">,
   HelpText<"Allow multiple definitions">;
 
 def as_needed: F<"as-needed">,
   HelpText<"Only set DT_NEEDED for shared libraries if used">;
 
+def call_graph_profile_file: S<"call-graph-profile-file">,
+  HelpText<"Layout sections to optimize the given callgraph">;
+
+def call_graph_profile_sort: F<"call-graph-profile-sort">,
+  HelpText<"Sort sections by call graph profile information">;
+
 // -chroot doesn't have a help text because it is an internal option.
 def chroot: S<"chroot">;
 
 def color_diagnostics: F<"color-diagnostics">,
   HelpText<"Use colors in diagnostics">;
 
 def color_diagnostics_eq: J<"color-diagnostics=">,
   HelpText<"Use colors in diagnostics">;

 defm Map: Eq<"Map">, HelpText<"Print a link map to the specified file">;
 
 def nostdlib: F<"nostdlib">,
   HelpText<"Only search directories specified on the command line">;
 
 def no_as_needed: F<"no-as-needed">,
   HelpText<"Always DT_NEEDED for shared libraries">;
 
+def no_call_graph_profile_sort: F<"no-call-graph-profile-sort">,
+  HelpText<"Don't sort sections by call graph profile information">;
+
 def no_color_diagnostics: F<"no-color-diagnostics">,
   HelpText<"Do not use colors in diagnostics">;
 
 def no_define_common: F<"no-define-common">,
   HelpText<"Do not assign space to common symbols">;
 
 def no_demangle: F<"no-demangle">,
   HelpText<"Do not demangle symbol names">;

lld/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 "CallGraphSort.h"
 #include "Config.h"
 #include "Filesystem.h"
 #include "LinkerScript.h"
 #include "MapFile.h"
 #include "OutputSections.h"
 #include "Relocations.h"
 #include "Strings.h"
 #include "SymbolTable.h"
findOrphanPos(std::vector<BaseCommand *>::iterator B,
   return I;
 }
 
 // If no layout was provided by linker script, we want to apply default
 // sorting for special input sections and handle --symbol-ordering-file.
 template <class ELFT> void Writer<ELFT>::sortInputSections() {
   assert(!Script->HasSectionsCommand);
 
+  // Use the rarely used option -call-graph-ordering-file to sort sections.
+  if (Config->CallGraphProfileSort && !Config->CallGraphProfile.empty()) {
+    DenseMap<const InputSectionBase *, int> OrderMap =
+      computeCallGraphProfileOrder();
+
+    if (OutputSection *Sec = findSection(".text"))
+      Sec->sort([&](InputSectionBase *S) { return OrderMap.lookup(S); });
+  }
+
   // Sort input sections by priority using the list provided
   // by --symbol-ordering-file.
   DenseMap<SectionBase *, int> Order = buildSectionOrder();
   if (!Order.empty())
     for (BaseCommand *Base : Script->SectionCommands)
       if (auto *Sec = dyn_cast<OutputSection>(Base))
         if (Sec->Live)
           Sec->sort([&](InputSectionBase *S) { return Order.lookup(S); });

lld/test/ELF/Inputs/cgprofile.txt

+5000 c a
+4000 c b
+0 d e
+18446744073709551615 e d
+18446744073709551611 f d
+18446744073709551612 f e
+6000 c h

lld/test/ELF/cgprofile-object.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2
+# RUN: llvm-readobj -symbols %t2 | FileCheck %s
+# RUN: ld.lld %t -o %t2 -no-call-graph-profile-sort
+# RUN: llvm-readobj -symbols %t2 | FileCheck %s --check-prefix=NOSORT
+
+    .section    .text.hot._Z4fooav,"ax",@progbits
+    .globl  _Z4fooav
+_Z4fooav:
+    retq
+
+    .section    .text.hot._Z4foobv,"ax",@progbits
+    .globl  _Z4foobv
+_Z4foobv:
+    retq
+
+    .section    .text.hot._Z3foov,"ax",@progbits
+    .globl  _Z3foov
+_Z3foov:
+    retq
+
+    .section    .text.hot._start,"ax",@progbits
+    .globl  _start
+_start:
+    retq
+
+
+    .cg_profile _start, _Z3foov, 1
+    .cg_profile _Z4fooav, _Z4foobv, 1
+    .cg_profile _Z3foov, _Z4fooav, 1
+
+# CHECK:          Name: _Z3foov
+# CHECK-NEXT:     Value: 0x201001
+# CHECK:          Name: _Z4fooav
+# CHECK-NEXT:     Value: 0x201002
+# CHECK:          Name: _Z4foobv
+# CHECK-NEXT:     Value: 0x201003
+# CHECK:          Name: _start
+# CHECK-NEXT:     Value: 0x201000
+  
+# NOSORT:          Name: _Z3foov
+# NOSORT-NEXT:     Value: 0x201002
+# NOSORT:          Name: _Z4fooav
+# NOSORT-NEXT:     Value: 0x201000
+# NOSORT:          Name: _Z4foobv
+# NOSORT-NEXT:     Value: 0x201001
+# NOSORT:          Name: _start
+# NOSORT-NEXT:     Value: 0x201003

lld/test/ELF/cgprofile.s

+# REQUIRES: x86
+#
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1
+# RUN: ld.lld %t1 -e a -o %t -call-graph-profile-file %p/Inputs/cgprofile.txt
+# RUN: llvm-readobj -symbols %t | FileCheck %s
+
+    .section .text.a,"ax",@progbits
+    .global a
+a:
+    .zero 20
+
+    .section .text.b,"ax",@progbits
+    .global b
+b:
+    .zero 1
+    
+    .section .text.c,"ax",@progbits
+    .global c
+c:
+    .zero 4095
+    
+    .section .text.d,"ax",@progbits
+    .global d
+d:
+    .zero 51
+    
+    .section .text.e,"ax",@progbits
+    .global e
+e:
+    .zero 42
+
+    .section .text.f,"ax",@progbits
+    .global f
+f:
+    .zero 42
+  
+    .section .text.g,"ax",@progbits
+    .global g
+g:
+  .zero 34
+  
+    .section .text.h,"ax",@progbits
+    .global h
+h:
+
+# CHECK:     Symbols [
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name:  (0)
+# CHECK-NEXT:    Value: 0x0
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Local (0x0)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: Undefined (0x0)
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: a
+# CHECK-NEXT:    Value: 0x202022
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: b
+# CHECK-NEXT:    Value: 0x202021
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: c
+# CHECK-NEXT:    Value: 0x201022
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: d
+# CHECK-NEXT:    Value: 0x20208A
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: e
+# CHECK-NEXT:    Value: 0x202060
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: f
+# CHECK-NEXT:    Value: 0x202036
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: g
+# CHECK-NEXT:    Value: 0x201000
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:  Symbol {
+# CHECK-NEXT:    Name: h
+# CHECK-NEXT:    Value: 0x201022
+# CHECK-NEXT:    Size: 0
+# CHECK-NEXT:    Binding: Global (0x1)
+# CHECK-NEXT:    Type: None (0x0)
+# CHECK-NEXT:    Other: 0
+# CHECK-NEXT:    Section: .text
+# CHECK-NEXT:  }
+# CHECK-NEXT:]

llvm/include/llvm/InitializePasses.h

 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&);
 void initializeBranchRelaxationPass(PassRegistry&);
 void initializeBreakCriticalEdgesPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
+void initializeCFGProfilePassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createSCEVAAWrapperPass();
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBoundsCheckingLegacyPass();
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCallGraphDOTPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
+      (void) llvm::createCFGProfilePass();
       (void) llvm::createCFLAndersAAWrapperPass();
       (void) llvm::createCFLSteensAAWrapperPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createLibCallsShrinkWrapPass();
       (void) llvm::createCalledValuePropagationPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createCostModelAnalysisPass();

llvm/include/llvm/MC/MCAssembler.h

public:
 
   // FIXME: This is a total hack, this should not be here. Once things are
   // factored so that the streamer has direct access to the .o writer, it can
   // disappear.
   MCLOHContainer &getLOHContainer() { return LOHContainer; }
   const MCLOHContainer &getLOHContainer() const {
     return const_cast<MCAssembler *>(this)->getLOHContainer();
   }
+
+  struct CGProfileEntry {
+    const MCSymbol *From;
+    const MCSymbol *To;
+    uint64_t Count;
+  };
+  std::vector<CGProfileEntry> CGProfile;
   /// @}
   /// \name Backend Data Access
   /// @{
 
   bool registerSection(MCSection &Section);
 
   void registerSymbol(const MCSymbol &Symbol, bool *Created = nullptr);
 

llvm/include/llvm/MC/MCELFStreamer.h

void EmitTBSSSymbol(MCSection *Section, MCSymbol *Symbol, uint64_t Size,
                       unsigned ByteAlignment = 0) override;
   void EmitValueImpl(const MCExpr *Value, unsigned Size,
                      SMLoc Loc = SMLoc()) override;
 
   void EmitIdent(StringRef IdentString) override;
 
   void EmitValueToAlignment(unsigned, int64_t, unsigned, unsigned) override;
 
+  void emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                          uint64_t Count) override;
+
   void FinishImpl() override;
 
   void EmitBundleAlignMode(unsigned AlignPow2) override;
   void EmitBundleLock(bool AlignToEnd) override;
   void EmitBundleUnlock() override;
 
 private:
   bool isBundleLocked() const;

llvm/include/llvm/MC/MCStreamer.h

public:
   virtual void EmitWinCFISaveXMM(unsigned Register, unsigned Offset,
                                  SMLoc Loc = SMLoc());
   virtual void EmitWinCFIPushFrame(bool Code, SMLoc Loc = SMLoc());
   virtual void EmitWinCFIEndProlog(SMLoc Loc = SMLoc());
   virtual void EmitWinEHHandler(const MCSymbol *Sym, bool Unwind, bool Except,
                                 SMLoc Loc = SMLoc());
   virtual void EmitWinEHHandlerData(SMLoc Loc = SMLoc());
 
+  virtual void emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                  uint64_t Count);
+
   /// Get the .pdata section used for the given section. Typically the given
   /// section is either the main .text section or some other COMDAT .text
   /// section, but it may be any section containing code.
   MCSection *getAssociatedPDataSection(const MCSection *TextSec);
 
   /// Get the .xdata section used for the given section.
   MCSection *getAssociatedXDataSection(const MCSection *TextSec);
 

llvm/include/llvm/Object/ELFTypes.h

 template <class ELFT> struct Elf_Verdef_Impl;
 template <class ELFT> struct Elf_Verdaux_Impl;
 template <class ELFT> struct Elf_Verneed_Impl;
 template <class ELFT> struct Elf_Vernaux_Impl;
 template <class ELFT> struct Elf_Versym_Impl;
 template <class ELFT> struct Elf_Hash_Impl;
 template <class ELFT> struct Elf_GnuHash_Impl;
 template <class ELFT> struct Elf_Chdr_Impl;
+template <class ELFT> struct Elf_CGProfile_Impl;
 
 template <endianness E, bool Is64> struct ELFType {
 private:
   template <typename Ty>
   using packed = support::detail::packed_endian_specific_integral<Ty, E, 2>;
 
 public:
   static const endianness TargetEndianness = E;
public:
   using Verdef = Elf_Verdef_Impl<ELFType<E, Is64>>;
   using Verdaux = Elf_Verdaux_Impl<ELFType<E, Is64>>;
   using Verneed = Elf_Verneed_Impl<ELFType<E, Is64>>;
   using Vernaux = Elf_Vernaux_Impl<ELFType<E, Is64>>;
   using Versym = Elf_Versym_Impl<ELFType<E, Is64>>;
   using Hash = Elf_Hash_Impl<ELFType<E, Is64>>;
   using GnuHash = Elf_GnuHash_Impl<ELFType<E, Is64>>;
   using Chdr = Elf_Chdr_Impl<ELFType<E, Is64>>;
+  using CGProfile = Elf_CGProfile_Impl<ELFType<E, Is64>>;
   using DynRange = ArrayRef<Dyn>;
   using ShdrRange = ArrayRef<Shdr>;
   using SymRange = ArrayRef<Sym>;
   using RelRange = ArrayRef<Rel>;
   using RelaRange = ArrayRef<Rela>;
   using PhdrRange = ArrayRef<Phdr>;
 
   using Half = packed<uint16_t>;

 struct Elf_Chdr_Impl<ELFType<TargetEndianness, true>> {
   LLVM_ELF_IMPORT_TYPES(TargetEndianness, true)
   Elf_Word ch_type;
   Elf_Word ch_reserved;
   Elf_Xword ch_size;
   Elf_Xword ch_addralign;
 };
 
+template <class ELFT>
+struct Elf_CGProfile_Impl {
+  LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
+  Elf_Word cgp_from;
+  Elf_Word cgp_to;
+  Elf_Xword cgp_weight;
+};
+
 // MIPS .reginfo section
 template <class ELFT>
 struct Elf_Mips_RegInfo;
 
 template <support::endianness TargetEndianness>
 struct Elf_Mips_RegInfo<ELFType<TargetEndianness, false>> {
   LLVM_ELF_IMPORT_TYPES(TargetEndianness, false)
   Elf_Word ri_gprmask;     // bit-mask of used general registers

llvm/include/llvm/Transforms/Instrumentation.h

struct SanitizerCoverageOptions {
 
   SanitizerCoverageOptions() = default;
 };
 
 // Insert SanitizerCoverage instrumentation.
 ModulePass *createSanitizerCoverageModulePass(
     const SanitizerCoverageOptions &Options = SanitizerCoverageOptions());
 
+ModulePass *createCFGProfilePass();
+
 /// \brief Calculate what to divide by to scale counts.
 ///
 /// Given the maximum count, calculate a divisor that will scale all the
 /// weights to strictly less than std::numeric_limits<uint32_t>::max().
 static inline uint64_t calculateCountScale(uint64_t MaxCount) {
   return MaxCount < std::numeric_limits<uint32_t>::max()
              ? 1
              : MaxCount / std::numeric_limits<uint32_t>::max() + 1;

llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp

 
 void TargetLoweringObjectFileELF::emitModuleMetadata(
     MCStreamer &Streamer, Module &M, const TargetMachine &TM) const {
   unsigned Version = 0;
   unsigned Flags = 0;
   StringRef Section;
 
   GetObjCImageInfo(M, Version, Flags, Section);
-  if (Section.empty())
-    return;
-
+  if (!Section.empty()) {
     auto &C = getContext();
     auto *S = C.getELFSection(Section, ELF::SHT_PROGBITS, ELF::SHF_ALLOC);
     Streamer.SwitchSection(S);
     Streamer.EmitLabel(C.getOrCreateSymbol(StringRef("OBJC_IMAGE_INFO")));
     Streamer.EmitIntValue(Version, 4);
     Streamer.EmitIntValue(Flags, 4);
     Streamer.AddBlankLine();
   }
 
+  SmallVector<Module::ModuleFlagEntry, 8> ModuleFlags;
+  M.getModuleFlagsMetadata(ModuleFlags);
+
+  MDNode *CFGProfile = nullptr;
+
+  for (const auto &MFE : ModuleFlags) {
+    StringRef Key = MFE.Key->getString();
+    if (Key == "CFG Profile") {
+      CFGProfile = cast<MDNode>(MFE.Val);
+      break;
+    }
+  }
+
+  if (!CFGProfile)
+    return;
+  /*MCSectionELF *Sec =
+      getContext().getELFSection(".note.llvm.callgraph", ELF::SHT_NOTE, 0);
+  Streamer.SwitchSection(Sec);
+  SmallString<256> Out;
+  for (const auto &Edge : CFGProfile->operands()) {
+    raw_svector_ostream O(Out);
+    MDNode *E = cast<MDNode>(Edge);
+    O << cast<MDString>(E->getOperand(0))->getString() << " "
+      << cast<MDString>(E->getOperand(1))->getString() << " "
+      << cast<ConstantAsMetadata>(E->getOperand(2))
+             ->getValue()
+             ->getUniqueInteger()
+             .getZExtValue()
+      << "\n";
+    Streamer.EmitBytes(O.str());
+    Out.clear();
+  }*/
+  for (const auto &Edge : CFGProfile->operands()) {
+    MDNode *E = cast<MDNode>(Edge);
+    const MCSymbol *From = Streamer.getContext().getOrCreateSymbol(
+        cast<MDString>(E->getOperand(0))->getString());
+    const MCSymbol *To = Streamer.getContext().getOrCreateSymbol(
+        cast<MDString>(E->getOperand(1))->getString());
+    uint64_t Count = cast<ConstantAsMetadata>(E->getOperand(2))
+                         ->getValue()
+                         ->getUniqueInteger()
+                         .getZExtValue();
+    Streamer.emitCGProfileEntry(From, To, Count);
+  }
+}
+
 MCSymbol *TargetLoweringObjectFileELF::getCFIPersonalitySymbol(
     const GlobalValue *GV, const TargetMachine &TM,
     MachineModuleInfo *MMI) const {
   unsigned Encoding = getPersonalityEncoding();
   if ((Encoding & 0x80) == DW_EH_PE_indirect)
     return getContext().getOrCreateSymbol(StringRef("DW.ref.") +
                                           TM.getSymbol(GV)->getName());
   if ((Encoding & 0x70) == DW_EH_PE_absptr)

llvm/lib/MC/ELFObjectWriter.cpp

for (MCSection &Sec : Asm) {
 
     SectionIndexMap[&Section] = addToSectionTable(&Section);
     if (RelSection) {
       SectionIndexMap[RelSection] = addToSectionTable(RelSection);
       Relocations.push_back(RelSection);
     }
   }
 
+  MCSectionELF *CGProfileSection = nullptr;
+  if (!Asm.CGProfile.empty()) {
+    CGProfileSection =
+      Ctx.getELFSection(".note.llvm.cgprofile", ELF::SHT_NOTE, 0, 16, "");
+    SectionIndexMap[CGProfileSection] = addToSectionTable(CGProfileSection);
+  }
+
   for (MCSectionELF *Group : Groups) {
     align(Group->getAlignment());
 
     // Remember the offset into the file for this section.
     uint64_t SecStart = getStream().tell();
 
     const MCSymbol *SignatureSymbol = Group->getGroup();
     assert(SignatureSymbol);
for (MCSectionELF *RelSection : Relocations) {
 
     writeRelocations(Asm,
                      cast<MCSectionELF>(*RelSection->getAssociatedSection()));
 
     uint64_t SecEnd = getStream().tell();
     SectionOffsets[RelSection] = std::make_pair(SecStart, SecEnd);
   }
 
+  if (CGProfileSection) {
+    uint64_t SecStart = getStream().tell();
+    for (const MCAssembler::CGProfileEntry &CGPE : Asm.CGProfile) {
+      write32(CGPE.From->getIndex());
+      write32(CGPE.To->getIndex());
+      write64(CGPE.Count);
+    }
+    uint64_t SecEnd = getStream().tell();
+    SectionOffsets[CGProfileSection] = std::make_pair(SecStart, SecEnd);
+  }
+
   {
     uint64_t SecStart = getStream().tell();
     const MCSectionELF *Sec = createStringTable(Ctx);
     uint64_t SecEnd = getStream().tell();
     SectionOffsets[Sec] = std::make_pair(SecStart, SecEnd);
   }
 
   uint64_t NaturalAlignment = is64Bit() ? 8 : 4;

llvm/lib/MC/MCAsmStreamer.cpp

void EmitWinCFISaveXMM(unsigned Register, unsigned Offset,
                          SMLoc Loc) override;
   void EmitWinCFIPushFrame(bool Code, SMLoc Loc) override;
   void EmitWinCFIEndProlog(SMLoc Loc) override;
 
   void EmitWinEHHandler(const MCSymbol *Sym, bool Unwind, bool Except,
                         SMLoc Loc) override;
   void EmitWinEHHandlerData(SMLoc Loc) override;
 
+  void emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                          uint64_t Count) override;
+
   void EmitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI,
                        bool PrintSchedInfo) override;
 
   void EmitBundleAlignMode(unsigned AlignPow2) override;
   void EmitBundleLock(bool AlignToEnd) override;
   void EmitBundleUnlock() override;
 
   bool EmitRelocDirective(const MCExpr &Offset, StringRef Name,

 
 void MCAsmStreamer::EmitWinCFIEndProlog(SMLoc Loc) {
   MCStreamer::EmitWinCFIEndProlog(Loc);
 
   OS << "\t.seh_endprologue";
   EmitEOL();
 }
 
+void MCAsmStreamer::emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                       uint64_t Count) {
+  OS << "\t.cg_profile ";
+  From->print(OS, MAI);
+  OS << ", ";
+  To->print(OS, MAI);
+  OS << ", " << Count;
+  EmitEOL();
+}
+
 void MCAsmStreamer::AddEncodingComment(const MCInst &Inst,
                                        const MCSubtargetInfo &STI,
                                        bool PrintSchedInfo) {
   raw_ostream &OS = GetCommentOS();
   SmallString<256> Code;
   SmallVector<MCFixup, 4> Fixups;
   raw_svector_ostream VecOS(Code);
   Emitter->encodeInstruction(Inst, VecOS, Fixups, STI);

llvm/lib/MC/MCELFStreamer.cpp

void MCELFStreamer::EmitValueToAlignment(unsigned ByteAlignment,
                                          unsigned ValueSize,
                                          unsigned MaxBytesToEmit) {
   if (isBundleLocked())
     report_fatal_error("Emitting values inside a locked bundle is forbidden");
   MCObjectStreamer::EmitValueToAlignment(ByteAlignment, Value,
                                          ValueSize, MaxBytesToEmit);
 }
 
+void MCELFStreamer::emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                       uint64_t Count) {
+  getAssembler().CGProfile.push_back({From, To, Count});
+}
+
 void MCELFStreamer::EmitIdent(StringRef IdentString) {
   MCSection *Comment = getAssembler().getContext().getELFSection(
       ".comment", ELF::SHT_PROGBITS, ELF::SHF_MERGE | ELF::SHF_STRINGS, 1, "");
   PushSection();
   SwitchSection(Comment);
   if (!SeenIdent) {
     EmitIntValue(0, 1);
     SeenIdent = true;

llvm/lib/MC/MCParser/ELFAsmParser.cpp

void Initialize(MCAsmParser &Parser) override {
     addDirectiveHandler<&ELFAsmParser::ParseDirectiveSymbolAttribute>(".local");
     addDirectiveHandler<
       &ELFAsmParser::ParseDirectiveSymbolAttribute>(".protected");
     addDirectiveHandler<
       &ELFAsmParser::ParseDirectiveSymbolAttribute>(".internal");
     addDirectiveHandler<
       &ELFAsmParser::ParseDirectiveSymbolAttribute>(".hidden");
     addDirectiveHandler<&ELFAsmParser::ParseDirectiveSubsection>(".subsection");
+    addDirectiveHandler<&ELFAsmParser::ParseDirectiveCGProfile>(".cg_profile");
   }
 
   // FIXME: Part of this logic is duplicated in the MCELFStreamer. What is
   // the best way for us to get access to it?
   bool ParseSectionDirectiveData(StringRef, SMLoc) {
     return ParseSectionSwitch(".data", ELF::SHT_PROGBITS,
                               ELF::SHF_WRITE | ELF::SHF_ALLOC,
                               SectionKind::getData());
public:
   bool ParseDirectivePrevious(StringRef, SMLoc);
   bool ParseDirectiveType(StringRef, SMLoc);
   bool ParseDirectiveIdent(StringRef, SMLoc);
   bool ParseDirectiveSymver(StringRef, SMLoc);
   bool ParseDirectiveVersion(StringRef, SMLoc);
   bool ParseDirectiveWeakref(StringRef, SMLoc);
   bool ParseDirectiveSymbolAttribute(StringRef, SMLoc);
   bool ParseDirectiveSubsection(StringRef, SMLoc);
+  bool ParseDirectiveCGProfile(StringRef, SMLoc);
 
 private:
   bool ParseSectionName(StringRef &SectionName);
   bool ParseSectionArguments(bool IsPush, SMLoc loc);
   unsigned parseSunStyleSectionFlags();
   bool maybeParseSectionType(StringRef &TypeName);
   bool parseMergeSize(int64_t &Size);
   bool parseGroup(StringRef &GroupName);
if (getLexer().isNot(AsmToken::EndOfStatement))
     return TokError("unexpected token in directive");
 
   Lex();
 
   getStreamer().SubSection(Subsection);
   return false;
 }
 
+/// ParseDirectiveCGProfile
+///  ::= .cg_profile identifier, identifier, <number>
+bool ELFAsmParser::ParseDirectiveCGProfile(StringRef, SMLoc) {
+  StringRef From;
+  if (getParser().parseIdentifier(From))
+    return TokError("expected identifier in directive");
+
+  if (getLexer().isNot(AsmToken::Comma))
+    return TokError("expected a comma");
+  Lex();
+
+  StringRef To;
+  if (getParser().parseIdentifier(To))
+    return TokError("expected identifier in directive");
+
+  if (getLexer().isNot(AsmToken::Comma))
+    return TokError("expected a comma");
+  Lex();
+
+  int64_t Count;
+  if (getParser().parseIntToken(
+          Count, "expected integer count in '.cg_profile' directive"))
+    return true;
+
+  if (getLexer().isNot(AsmToken::EndOfStatement))
+    return TokError("unexpected token in directive");
+
+  MCSymbol *FromSym = getContext().getOrCreateSymbol(From);
+  MCSymbol *ToSym = getContext().getOrCreateSymbol(To);
+
+  getStreamer().emitCGProfileEntry(FromSym, ToSym, Count);
+  return false;
+}
+
 namespace llvm {
 
 MCAsmParserExtension *createELFAsmParser() {
   return new ELFAsmParser;
 }
 
 } // end namespace llvm

llvm/lib/MC/MCStreamer.cpp

 void MCStreamer::EmitWinEHHandlerData(SMLoc Loc) {
   WinEH::FrameInfo *CurFrame = EnsureValidWinFrameInfo(Loc);
   if (!CurFrame)
     return;
   if (CurFrame->ChainedParent)
     getContext().reportError(Loc, "Chained unwind areas can't have handlers!");
 }
 
+void MCStreamer::emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                    uint64_t Count) {
+}
+
 static MCSection *getWinCFISection(MCContext &Context, unsigned *NextWinCFIID,
                                    MCSection *MainCFISec,
                                    const MCSection *TextSec) {
   // If this is the main .text section, use the main unwind info section.
   if (TextSec == Context.getObjectFileInfo()->getTextSection())
     return MainCFISec;
 
   const auto *TextSecCOFF = cast<MCSectionCOFF>(TextSec);

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
 
   // GlobalOpt already deletes dead functions and globals, at -O2 try a
   // late pass of GlobalDCE.  It is capable of deleting dead cycles.
   if (OptLevel > 1) {
     MPM.add(createGlobalDCEPass());         // Remove dead fns and globals.
     MPM.add(createConstantMergePass());     // Merge dup global constants
   }
 
+  MPM.add(createCFGProfilePass());
+
   if (MergeFunctions)
     MPM.add(createMergeFunctionsPass());
 
   // LoopSink pass sinks instructions hoisted by LICM, which serves as a
   // canonicalization pass that enables other optimizations. As a result,
   // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
   // result too early.
   MPM.add(createLoopSinkPass());

llvm/lib/Transforms/Instrumentation/CFGProfile.cpp

+//===-- CFGProfile.cpp ----------------------------------------------------===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Instrumentation.h"
+
+#include <array>
+
+using namespace llvm;
+
+class CFGProfilePass : public ModulePass {
+public:
+  static char ID;
+
+  CFGProfilePass() : ModulePass(ID) {
+    initializeCFGProfilePassPass(
+      *PassRegistry::getPassRegistry());
+  }
+
+  StringRef getPassName() const override { return "CFGProfilePass"; }
+
+private:
+  bool runOnModule(Module &M) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  }
+};
+
+bool CFGProfilePass::runOnModule(Module &M) {
+  if (skipModule(M))
+    return false;
+
+  llvm::DenseMap<std::pair<StringRef, StringRef>, uint64_t> Counts;
+
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
+    auto &BFI = getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+    for (auto &BB : F) {
+      Optional<uint64_t> BBCount = BFI.getBlockProfileCount(&BB);
+      if (!BBCount)
+        continue;
+      for (auto &I : BB) {
+        auto *CI = dyn_cast<CallInst>(&I);
+        if (!CI)
+          continue;
+        Function *CalledF = CI->getCalledFunction();
+        if (!CalledF || CalledF->isIntrinsic())
+          continue;
+
+        uint64_t &Count =
+            Counts[std::make_pair(F.getName(), CalledF->getName())];
+        Count = SaturatingAdd(Count, *BBCount);
+      }
+    }
+  }
+
+  if (Counts.empty())
+    return false;
+
+  LLVMContext &Context = M.getContext();
+  MDBuilder MDB(Context);
+  std::vector<Metadata *> Nodes;
+
+  for (auto E : Counts) {
+    SmallVector<Metadata *, 3> Vals;
+    Vals.push_back(MDB.createString(E.first.first));
+    Vals.push_back(MDB.createString(E.first.second));
+    Vals.push_back(MDB.createConstant(
+        ConstantInt::get(Type::getInt64Ty(Context), E.second)));
+    Nodes.push_back(MDNode::get(Context, Vals));
+  }
+
+  M.addModuleFlag(Module::Append, "CFG Profile", MDNode::get(Context, Nodes));
+
+  return true;
+}
+
+char CFGProfilePass::ID = 0;
+INITIALIZE_PASS_BEGIN(CFGProfilePass, "cfg-profile",
+  "Generate profile information from the CFG.", false, false)
+  INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+  INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+  INITIALIZE_PASS_END(CFGProfilePass, "cfg-profile",
+    "Generate profile information from the CFG.", false, false)
+
+ModulePass *llvm::createCFGProfilePass() {
+  return new CFGProfilePass();
+}

llvm/lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
+  CFGProfile.cpp
   DataFlowSanitizer.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
   IndirectCallPromotion.cpp
   Instrumentation.cpp
   InstrProfiling.cpp
   PGOInstrumentation.cpp
   PGOMemOPSizeOpt.cpp

llvm/lib/Transforms/Instrumentation/Instrumentation.cpp

 
 /// initializeInstrumentation - Initialize all passes in the TransformUtils
 /// library.
 void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeAddressSanitizerPass(Registry);
   initializeAddressSanitizerModulePass(Registry);
   initializeBoundsCheckingLegacyPassPass(Registry);
   initializeGCOVProfilerLegacyPassPass(Registry);
+  initializeCFGProfilePassPass(Registry);
   initializePGOInstrumentationGenLegacyPassPass(Registry);
   initializePGOInstrumentationUseLegacyPassPass(Registry);
   initializePGOIndirectCallPromotionLegacyPassPass(Registry);
   initializePGOMemOPSizeOptLegacyPassPass(Registry);
   initializeInstrProfilingLegacyPassPass(Registry);
   initializeMemorySanitizerPass(Registry);
   initializeThreadSanitizerPass(Registry);
   initializeSanitizerCoverageModulePass(Registry);

llvm/tools/llvm-readobj/ELFDumper.cpp

#define TYPEDEF_ELF_TYPES(ELFT)                                                \
   using Elf_Hash = typename ELFO::Elf_Hash;                                    \
   using Elf_GnuHash = typename ELFO::Elf_GnuHash;                              \
   using Elf_Sym_Range = typename ELFO::Elf_Sym_Range;                          \
   using Elf_Versym = typename ELFO::Elf_Versym;                                \
   using Elf_Verneed = typename ELFO::Elf_Verneed;                              \
   using Elf_Vernaux = typename ELFO::Elf_Vernaux;                              \
   using Elf_Verdef = typename ELFO::Elf_Verdef;                                \
   using Elf_Verdaux = typename ELFO::Elf_Verdaux;                              \
+  using Elf_CGProfile = typename ELFT::CGProfile;                              \
   using uintX_t = typename ELFO::uintX_t;
 
 namespace {
 
 template <class ELFT> class DumpStyle;
 
 /// Represents a contiguous uniform range in the file. We cannot just create a
 /// range directly because when creating one of these from the .dynamic table
public:
   void printMipsABIFlags() override;
   void printMipsReginfo() override;
   void printMipsOptions() override;
 
   void printStackMap() const override;
 
   void printHashHistogram() override;
 
+  void printCGProfile() override;
+
   void printNotes() override;
 
 private:
   std::unique_ptr<DumpStyle<ELFT>> ELFDumperStyle;
 
   TYPEDEF_ELF_TYPES(ELFT)
 
   DynRegionInfo checkDRI(DynRegionInfo DRI) {
private:
   DynRegionInfo DynPLTRelRegion;
   DynRegionInfo DynSymRegion;
   DynRegionInfo DynamicTable;
   StringRef DynamicStringTable;
   StringRef SOName;
   const Elf_Hash *HashTable = nullptr;
   const Elf_GnuHash *GnuHashTable = nullptr;
   const Elf_Shdr *DotSymtabSec = nullptr;
+  const Elf_Shdr *DotCGProfileSec = nullptr;
   StringRef DynSymtabName;
   ArrayRef<Elf_Word> ShndxTable;
 
   const Elf_Shdr *dot_gnu_version_sec = nullptr;   // .gnu.version
   const Elf_Shdr *dot_gnu_version_r_sec = nullptr; // .gnu.version_r
   const Elf_Shdr *dot_gnu_version_d_sec = nullptr; // .gnu.version_d
 
   // Records for each version index the corresponding Verdef or Vernaux entry.
public:
   Elf_Sym_Range dynamic_symbols() const {
     return DynSymRegion.getAsArrayRef<Elf_Sym>();
   }
 
   Elf_Rel_Range dyn_rels() const;
   Elf_Rela_Range dyn_relas() const;
   std::string getFullSymbolName(const Elf_Sym *Symbol, StringRef StrTable,
                                 bool IsDynamic) const;
+  StringRef getStaticSymbolName(uint32_t Index) const;
 
   void printSymbolsHelper(bool IsDynamic) const;
   const Elf_Shdr *getDotSymtabSec() const { return DotSymtabSec; }
+  const Elf_Shdr *getDotCGProfileSec() const { return DotCGProfileSec; }
   ArrayRef<Elf_Word> getShndxTable() const { return ShndxTable; }
   StringRef getDynamicStringTable() const { return DynamicStringTable; }
   const DynRegionInfo &getDynRelRegion() const { return DynRelRegion; }
   const DynRegionInfo &getDynRelaRegion() const { return DynRelaRegion; }
   const DynRegionInfo &getDynPLTRelRegion() const { return DynPLTRelRegion; }
   const Elf_Hash *getHashTable() const { return HashTable; }
   const Elf_GnuHash *getGnuHashTable() const { return GnuHashTable; }
 };
public:
   virtual void printDynamicRelocations(const ELFFile<ELFT> *Obj) = 0;
   virtual void printSymtabMessage(const ELFFile<ELFT> *obj, StringRef Name,
                                   size_t Offset) {}
   virtual void printSymbol(const ELFFile<ELFT> *Obj, const Elf_Sym *Symbol,
                            const Elf_Sym *FirstSym, StringRef StrTable,
                            bool IsDynamic) = 0;
   virtual void printProgramHeaders(const ELFFile<ELFT> *Obj) = 0;
   virtual void printHashHistogram(const ELFFile<ELFT> *Obj) = 0;
+  virtual void printCGProfile(const ELFFile<ELFT> *Obj) = 0;
   virtual void printNotes(const ELFFile<ELFT> *Obj) = 0;
   const ELFDumper<ELFT> *dumper() const { return Dumper; }
 
 private:
   const ELFDumper<ELFT> *Dumper;
 };
 
 template <typename ELFT> class GNUStyle : public DumpStyle<ELFT> {
public:
   void printSections(const ELFO *Obj) override;
   void printSymbols(const ELFO *Obj) override;
   void printDynamicSymbols(const ELFO *Obj) override;
   void printDynamicRelocations(const ELFO *Obj) override;
   void printSymtabMessage(const ELFO *Obj, StringRef Name,
                           size_t Offset) override;
   void printProgramHeaders(const ELFO *Obj) override;
   void printHashHistogram(const ELFFile<ELFT> *Obj) override;
+  void printCGProfile(const ELFFile<ELFT> *Obj) override;
   void printNotes(const ELFFile<ELFT> *Obj) override;
 
 private:
   struct Field {
     StringRef Str;
     unsigned Column;
 
     Field(StringRef S, unsigned Col) : Str(S), Column(Col) {}
public:
   void printRelocations(const ELFO *Obj) override;
   void printRelocations(const Elf_Shdr *Sec, const ELFO *Obj);
   void printSections(const ELFO *Obj) override;
   void printSymbols(const ELFO *Obj) override;
   void printDynamicSymbols(const ELFO *Obj) override;
   void printDynamicRelocations(const ELFO *Obj) override;
   void printProgramHeaders(const ELFO *Obj) override;
   void printHashHistogram(const ELFFile<ELFT> *Obj) override;
+  void printCGProfile(const ELFFile<ELFT> *Obj) override;
   void printNotes(const ELFFile<ELFT> *Obj) override;
 
 private:
   void printRelocation(const ELFO *Obj, Elf_Rela Rel, const Elf_Shdr *SymTab);
   void printDynamicRelocation(const ELFO *Obj, Elf_Rela Rel);
   void printSymbol(const ELFO *Obj, const Elf_Sym *Symbol, const Elf_Sym *First,
                    StringRef StrTable, bool IsDynamic) override;
 
std::string ELFDumper<ELFT>::getFullSymbolName(const Elf_Sym *Symbol,
   bool IsDefault;
   StringRef Version = getSymbolVersion(StrTable, &*Symbol, IsDefault);
   FullSymbolName += (IsDefault ? "@@" : "@");
   FullSymbolName += Version;
   return FullSymbolName;
 }
 
 template <typename ELFT>
+StringRef ELFDumper<ELFT>::getStaticSymbolName(uint32_t Index) const {
+  StringRef StrTable = unwrapOrError(Obj->getStringTableForSymtab(*DotSymtabSec));
+  Elf_Sym_Range Syms = unwrapOrError(Obj->symbols(DotSymtabSec));
+  if (Index >= Syms.size())
+    reportError("Invalid symbol index");
+  const Elf_Sym *Sym = &Syms[Index];
+  return unwrapOrError(Sym->getName(StrTable));
+}
+
+template <typename ELFT>
 static void
 getSectionNameIndex(const ELFFile<ELFT> &Obj, const typename ELFT::Sym *Symbol,
                     const typename ELFT::Sym *FirstSym,
                     ArrayRef<typename ELFT::Word> ShndxTable,
                     StringRef &SectionName, unsigned &SectionIndex) {
   SectionIndex = Symbol->st_shndx;
   if (Symbol->isUndefined())
     SectionName = "Undefined";
case ELF::SHT_GNU_verdef:
         reportError("Multiple SHT_GNU_verdef");
       dot_gnu_version_d_sec = &Sec;
       break;
     case ELF::SHT_GNU_verneed:
       if (dot_gnu_version_r_sec != nullptr)
         reportError("Multiple SHT_GNU_verneed");
       dot_gnu_version_r_sec = &Sec;
       break;
+    case ELF::SHT_NOTE:
+      if (unwrapOrError(Obj->getSectionName(&Sec)) != ".note.llvm.cgprofile")
+        break;
+      if (DotCGProfileSec != nullptr)
+        reportError("Multiple .note.llvm.cgprofile");
+      DotCGProfileSec = &Sec;
     }
   }
 
   parseDynamicTable(LoadSegments);
 
   if (opts::Output == opts::GNU)
     ELFDumperStyle.reset(new GNUStyle<ELFT>(Writer, this));
   else

 void ELFDumper<ELFT>::printDynamicSymbols() {
   ELFDumperStyle->printDynamicSymbols(Obj);
 }
 
 template <class ELFT> void ELFDumper<ELFT>::printHashHistogram() {
   ELFDumperStyle->printHashHistogram(Obj);
 }
 
+template <class ELFT> void ELFDumper<ELFT>::printCGProfile() {
+  ELFDumperStyle->printCGProfile(Obj);
+}
+
 template <class ELFT> void ELFDumper<ELFT>::printNotes() {
   ELFDumperStyle->printNotes(Obj);
 }
 
 #define LLVM_READOBJ_TYPE_CASE(name) \
   case DT_##name: return #name
 
 static const char *getTypeString(unsigned Arch, uint64_t Type) {
for (size_t I = 0; I <MaxChain; I++) {
       CumulativeNonZero += Count[I] * I;
       OS << format("%7lu  %-10lu (%5.1f%%)     %5.1f%%\n", I, Count[I],
                    (Count[I] * 100.0) / NBucket,
                    (CumulativeNonZero * 100.0) / TotalSyms);
     }
   }
 }
 
+template <class ELFT>
+void GNUStyle<ELFT>::printCGProfile(const ELFFile<ELFT> *Obj) {
+  OS<< "GNUStyle::printCGProfile not implemented\n";
+}
+
 static std::string getGNUNoteTypeName(const uint32_t NT) {
   static const struct {
     uint32_t ID;
     const char *Name;
   } Notes[] = {
       {ELF::NT_GNU_ABI_TAG, "NT_GNU_ABI_TAG (ABI version tag)"},
       {ELF::NT_GNU_HWCAP, "NT_GNU_HWCAP (DSO-supplied software HWCAP info)"},
       {ELF::NT_GNU_BUILD_ID, "NT_GNU_BUILD_ID (unique build ID bitstring)"},
void LLVMStyle<ELFT>::printProgramHeaders(const ELFO *Obj) {
   }
 }
 
 template <class ELFT>
 void LLVMStyle<ELFT>::printHashHistogram(const ELFFile<ELFT> *Obj) {
   W.startLine() << "Hash Histogram not implemented!\n";
 }
 
+
+
+template <class ELFT>
+void LLVMStyle<ELFT>::printCGProfile(const ELFFile<ELFT> *Obj) {
+  ListScope L(W, "CGProfile");
+  if (!this->dumper()->getDotCGProfileSec())
+    return;
+  auto CGProfile = unwrapOrError(Obj->template getSectionContentsAsArray<Elf_CGProfile>(this->dumper()->getDotCGProfileSec()));
+  for (const Elf_CGProfile &CGPE : CGProfile) {
+    DictScope D(W, "CGProfileEntry");
+    W.printNumber("From", this->dumper()->getStaticSymbolName(CGPE.cgp_from), CGPE.cgp_from);
+    W.printNumber("To", this->dumper()->getStaticSymbolName(CGPE.cgp_to), CGPE.cgp_to);
+    W.printNumber("Weight", CGPE.cgp_weight);
+  }
+}
+
 template <class ELFT>
 void LLVMStyle<ELFT>::printNotes(const ELFFile<ELFT> *Obj) {
   W.startLine() << "printNotes not implemented!\n";
 }

llvm/tools/llvm-readobj/ObjDumper.h

public:
   virtual void printNeededLibraries() { }
   virtual void printProgramHeaders() { }
   virtual void printHashTable() { }
   virtual void printGnuHashTable() { }
   virtual void printLoadName() {}
   virtual void printVersionInfo() {}
   virtual void printGroupSections() {}
   virtual void printHashHistogram() {}
+  virtual void printCGProfile() {}
   virtual void printNotes() {}
 
   // Only implemented for ARM ELF at this time.
   virtual void printAttributes() { }
 
   // Only implemented for MIPS ELF at this time.
   virtual void printMipsPLTGOT() { }
   virtual void printMipsABIFlags() { }

llvm/tools/llvm-readobj/llvm-readobj.cpp

namespace opts {
   cl::alias SectionGroupsShort("g", cl::desc("Alias for -elf-sections-groups"),
                                cl::aliasopt(SectionGroups));
   cl::opt<bool> HashHistogram(
       "elf-hash-histogram",
       cl::desc("Display bucket list histogram for hash sections"));
   cl::alias HashHistogramShort("I", cl::desc("Alias for -elf-hash-histogram"),
                                cl::aliasopt(HashHistogram));
 
+  cl::opt<bool> CGProfile("elf-cg-profile", cl::desc("Display callgraph profile section"));
+
   cl::opt<OutputStyleTy>
       Output("elf-output-style", cl::desc("Specify ELF dump style"),
              cl::values(clEnumVal(LLVM, "LLVM default style"),
                         clEnumVal(GNU, "GNU readelf style")),
              cl::init(LLVM));
 } // namespace opts
 
 namespace llvm {
if (isMipsArch(Obj->getArch())) {
         Dumper->printMipsReginfo();
       if (opts::MipsOptions)
         Dumper->printMipsOptions();
     }
     if (opts::SectionGroups)
       Dumper->printGroupSections();
     if (opts::HashHistogram)
       Dumper->printHashHistogram();
+    if (opts::CGProfile)
+      Dumper->printCGProfile();
     if (opts::Notes)
       Dumper->printNotes();
   }
   if (Obj->isCOFF()) {
     if (opts::COFFImports)
       Dumper->printCOFFImports();
     if (opts::COFFExports)
       Dumper->printCOFFExports();