[ELF] Dump symbols ordered by profiled guided section layout to file.

[tcwang]

Summary

In D36351, Call-Chain Clustering (C3) heuristic is implemented with
option --call-graph-ordering-file <file>.
This patch adds a flag --print-symbol-order=<file> to LLD, and when specified,
it prints out the symbols ordered by the heuristics to the file.
The symbols printout is helpful to those who want to understand the
heuristics and want to reproduce the ordering with --symbol-ordering-file
in later pass.

[ruiu]

lld/ELF/CallGraphSort.cpp

230

This is obvious, no need to explain by comment.

231

This looks too fancy compared to other messages such as one in MapFile.cpp. Let's make it less fancy.

I'd make the first line "Symbols ordered by call-chain clustering:\n", followed by a list of symbols, terminated by a blank line.

236

Are you sure that all input sections have a name?

lld/test/ELF/cgprofile-print.s

8

This does not seem to test the feature that you want to use. Don't you want to print out the sorting order as a result of parsing .llvm.call-graph-profile sections, do you?

[tcwang]

Fixing the comments.

[tcwang]

Thank you so much for the comments! Do you care to elaborate more on the test? I am not sure what I should test? Thanks!

lld/ELF/CallGraphSort.cpp

236

Not sure... But if the section doesn't, should I print an empty line, or just skip it?

lld/test/ELF/cgprofile-print.s

8

I am sorry that I think I am not sure I understand the comment completely. I was trying to add --verbose to LLD while passing in a call graph file and check the standard print with the expected ordering. (And I have removed the checks in the object file, since this check should be done in another test already.) Should I test something else instead?

[pcc]

lld/ELF/CallGraphSort.cpp

235

Should this go to a file with a user-specified name (without the header) instead of stdout? I'd expect the output of this to be consumed by a script, and sending it to a file would probably make it easier for said script to consume.

Also, should this be listing the symbols instead of the sections if the intent is to pass this to --symbol-ordering-file?

[ruiu]

lld/ELF/CallGraphSort.cpp

236

I don't think printing out a blank line is useful, but what I wanted to ask is if it is ever possible to be unnamed. We shouldn't guard it against an empty name "just in case".

lld/test/ELF/cgprofile-print.s

8

I thought that you wanted to print a result of a compiler-generated callgraph data stored into .llvm.call-graph-profile sections (there's such feature in lld and LLVM). If that's not the case, never mind.

[tcwang]

Adding check against empty InputSection names, and don't print out empty names.

[tcwang]

Thanks again for the comments!

lld/ELF/CallGraphSort.cpp

235

I strongly agree that these suggestions would improve our lives if we want to use the outputs to feed --symbol-ordering-file in later pass. (Actually, right now I have to use a separate script to process the standard output and removing the headers to generate order file.)

I'd love to improve this part, if it is OK to add a flag to support it. (And do you have any suggestions on the name of the flag?) Also, do you have some suggestions how to remove the headers cleanly? I don't see there's an option to remove the added prefix in the Name field of InputSectionBase? I don't think I should just try to remove ".text" (or ".text.hot" in some cases). Thank you!

236

I do see empty Name when testing against some programs. Maybe we should check empty Name before printing to avoid empty lines?

lld/test/ELF/cgprofile-print.s

8

I think this option --call-graph-ordering-file is consuming the call graph and directly generate a map of sections with order. I think I only need to print out the ordering in the map for this purpose. So that's why I test it against.

[ruiu]

lld/ELF/CallGraphSort.cpp

235

OK, that's fine. If that's the case, print out only symbol names to the file (without the header line). As to the option name, --print-symbol-order=FILENAME?

[tcwang]

Add a flag to save the output. Also printing out the symbol names of the ordering, instead of
the section names.

[tcwang]

lld/ELF/CallGraphSort.cpp

235

Thanks!

[tcwang]

Update title.

[ruiu]

lld/ELF/CallGraphSort.cpp

243

We do not use auto unless its type is obvious from right-hand side.

auto* Foo -> auto *Foo

246–247

You don't need to cast -- I think you can directly compare Sections[SecIndex] == D->Section.

lld/ELF/Driver.cpp

831 ↗

(On Diff #190525)

Config members has the same name as their corresponding command line options, so please name it PrintSymbolOrder.

[tcwang]

Fix comments. Add one more test to test the outputs of the flag can be used to
reproduce the order with --symbol-ordering-file

[tcwang]

Thanks!

lld/ELF/CallGraphSort.cpp

243

Ok. I will not use auto in this case. Thanks!

lld/ELF/Driver.cpp

831 ↗

(On Diff #190525)

Ok. I'll change the name.

[ruiu]

lld/ELF/CallGraphSort.cpp

243

Let's avoid using the same name for a variable and a class. I believe you have shadowed class Symbol by a variable Symbol. That's confusing. A common variable name is Sym.

[tcwang]

Fix comments

[tcwang]

lld/ELF/CallGraphSort.cpp

243

Oh, right. I'll fix it.

[MaskRay]

lld/ELF/Options.td

278 ↗

(On Diff #190538)

--call-graph-ordering file

[tcwang]

Fix comments

[tcwang]

lld/ELF/Options.td

278 ↗

(On Diff #190538)

Thanks!

[tcwang]

Ping. I think I have addressed all the comments here. Please let me know if there are more concerns to address. Thanks!

[ruiu]

lld/ELF/CallGraphSort.cpp

244

So I think that checking name is fragile. What do you actually want to skip by doing this?

lld/ELF/Driver.cpp

1477 ↗

(On Diff #190644)

80 cols.

lld/ELF/Options.td

278 ↗

(On Diff #190644)

This help message seem a little bit foreign compared to other help messages. A more natural help message would be probably something this:

Print a symbol order specified by --call-graph-ordering-file into to the specified file

Be careful not to put a full stop at the end of a help message.

lld/test/ELF/cgprofile-print.s

36–38

Remove trailing extra newlines.

[tcwang]

Fix comments

[tcwang]

lld/ELF/CallGraphSort.cpp

244

Because without this checking, I can get two symbols in the file that both match section. One of them is empty name. I wanted to use this filter out that symbol. Plus the goal of this part is to find out a symbol name from the file that is in the section. So empty-named symbols should be ignored?

[tcwang]

Fix comments to filter out section-typed symbols, instead of empty named ones.

[tcwang]

lld/ELF/CallGraphSort.cpp

244

Change the empty name check to symbol type check. If a symbol is section, no need to do the matching below.

[ruiu]

lld/ELF/CallGraphSort.cpp

243

So the cost of this code is O(n*m) where n is there number of the sorted sections and n is the number of the symbols in each file. I don't think this code needs to be super fast, as this is not in the usual code path. If the performance becomes a problem, let's revisit to optimize. I'm ok with this code for now.

lld/ELF/Driver.cpp

1475 ↗

(On Diff #192531)

I don't think we need this guard, as this is a minor feature. Can you remove this code?

[tcwang]

Fix comments.

[Bigcheese]

lld/ELF/Driver.cpp

1475 ↗

(On Diff #192531)

Why not be consistent here?

[ruiu]

LGTM

[ruiu]

lld/ELF/Driver.cpp

1475 ↗

(On Diff #192531)

We could have many more features that writes something to a file, but I don't want to add two lines of code every time we add such feature. I'd remove MapFile rather than adding all files here if it needs to be consistent.

lld/ELF/CallGraphSort.cpp

DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
   // Generate order.
   DenseMap<const InputSectionBase *, int> OrderMap;
   ssize_t CurOrder = 1;
 
   for (const Cluster &C : Clusters)
     for (int SecIndex : C.Sections)
       OrderMap[Sections[SecIndex]] = CurOrder++;
 
+  if (errorHandler().Verbose) {
+    // If user passes --verbose to LLD , print out the symbols ordered by C3.
+    outs() << "******** Symbols ordered by call-chain clustering ********\n";
+    // Print the symbols ordered by C3, in the order of increasing CurOrder
+    // Instead of sorting all the OrderMap, just repeat the loops above.
+    for (const Cluster &C : Clusters)
+      for (int SecIndex : C.Sections)
+        outs() << Sections[SecIndex]->Name << "\n";
+    outs() << "**********************************************************\n";
+  }
+
   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();
 }

lld/test/ELF/cgprofile-print.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "A B 5" > %t.call_graph
+# RUN: echo "B C 50" >> %t.call_graph
+# RUN: echo "C D 40" >> %t.call_graph
+# RUN: echo "D B 10" >> %t.call_graph
+# RUN: ld.lld -e A %t --call-graph-ordering-file %t.call_graph -o %t2 --verbose | FileCheck %s --check-prefix=VERBOSE
+# RUN: llvm-readobj -symbols %t2 | FileCheck %s
+
+# CHECK:      Name: A
+# CHECK-NEXT: Value: 0x201003
+# CHECK:      Name: B
+# CHECK-NEXT: Value: 0x201000
+# CHECK:      Name: C
+# CHECK-NEXT: Value: 0x201001
+# CHECK:      Name: D
+# CHECK-NEXT: Value: 0x201002
+
+.section    .text.A,"ax",@progbits
+.globl  A
+A:
+ nop
+
+.section    .text.B,"ax",@progbits
+.globl  B
+B:
+ nop
+
+.section    .text.C,"ax",@progbits
+.globl  C
+C:
+ nop
+
+.section    .text.D,"ax",@progbits
+.globl  D
+D:
+ nop
+
+
+# VERBOSE: ******** Symbols ordered by call-chain clustering ********
+# VERBOSE-NEXT: .text.B
+# VERBOSE-NEXT: .text.C
+# VERBOSE-NEXT: .text.D
+# VERBOSE-NEXT: .text.A
+# VERBOSE-NEXT: **********************************************************