[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

9

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

9

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

9

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

9

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

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

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

--call-graph-ordering file

[tcwang]

Fix comments

[tcwang]

lld/ELF/Options.td

278

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

80 cols.

lld/ELF/Options.td

278

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

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

Why not be consistent here?

[ruiu]

LGTM

[ruiu]

lld/ELF/Driver.cpp

1475

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 (!Config->PrintSymbolOrderToFile.empty()) {
+    std::error_code EC;
+    raw_fd_ostream OS(Config->PrintSymbolOrderToFile, EC, sys::fs::F_None);
+    if (EC) {
+      error("cannot open " + Config->PrintSymbolOrderToFile + ": " + EC.message());
+      return OrderMap;
+    }
+
+    // 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)
+        // Search all the symbols in the file of the section
+        // and find out a Defined symbol with name that is within the section.
+        for (auto* Symbol: Sections[SecIndex]->File->getSymbols())
+          if (!Symbol->getName().empty())
+            if (auto* D = dyn_cast<Defined>(Symbol))
+              if (auto* IS = dyn_cast_or_null<InputSectionBase>(D->Section))
+                if (Sections[SecIndex] == dyn_cast<InputSectionBase>(IS->Repl))
+                  OS << Symbol->getName() << "\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/ELF/Config.h

struct Configuration {
   llvm::StringRef LTONewPmPasses;
   llvm::StringRef LTOObjPath;
   llvm::StringRef LTOSampleProfile;
   llvm::StringRef MapFile;
   llvm::StringRef OutputFile;
   llvm::StringRef OptRemarksFilename;
   llvm::StringRef OptRemarksPasses;
   llvm::StringRef ProgName;
+  llvm::StringRef PrintSymbolOrderToFile;
   llvm::StringRef SoName;
   llvm::StringRef Sysroot;
   llvm::StringRef ThinLTOCacheDir;
   llvm::StringRef ThinLTOIndexOnlyArg;
   std::pair<llvm::StringRef, llvm::StringRef> ThinLTOObjectSuffixReplace;
   std::pair<llvm::StringRef, llvm::StringRef> ThinLTOPrefixReplace;
   std::string Rpath;
   std::vector<VersionDefinition> VersionDefinitions;

lld/ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->Optimize = args::getInteger(Args, OPT_O, 1);
   Config->OrphanHandling = getOrphanHandling(Args);
   Config->OutputFile = Args.getLastArgValue(OPT_o);
   Config->Pie = Args.hasFlag(OPT_pie, OPT_no_pie, false);
   Config->PrintIcfSections =
       Args.hasFlag(OPT_print_icf_sections, OPT_no_print_icf_sections, false);
   Config->PrintGcSections =
       Args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
+  Config->PrintSymbolOrderToFile =
+      Args.getLastArgValue(OPT_print_symbol_order);
   Config->Rpath = getRpath(Args);
   Config->Relocatable = Args.hasArg(OPT_relocatable);
   Config->SaveTemps = Args.hasArg(OPT_save_temps);
   Config->SearchPaths = args::getStrings(Args, OPT_library_path);
   Config->SectionStartMap = getSectionStartMap(Args);
   Config->Shared = Args.hasArg(OPT_shared);
   Config->SingleRoRx = Args.hasArg(OPT_no_rosegment);
   Config->SoName = Args.getLastArgValue(OPT_soname);
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
 
   // Fail early if the output file or map file is not writable. If a user has a
   // long link, e.g. due to a large LTO link, they do not wish to run it and
   // find that it failed because there was a mistake in their command-line.
   if (auto E = tryCreateFile(Config->OutputFile))
     error("cannot open output file " + Config->OutputFile + ": " + E.message());
   if (auto E = tryCreateFile(Config->MapFile))
     error("cannot open map file " + Config->MapFile + ": " + E.message());
+  // Fail early too if the symbol order file is not writable
+  if (auto E = tryCreateFile(Config->PrintSymbolOrderToFile))
+    error("cannot open symbol order output file " + Config->PrintSymbolOrderToFile + ": " + E.message());
   if (errorCount())
     return;
 
   // Use default entry point name if no name was given via the command
   // line nor linker scripts. For some reason, MIPS entry point name is
   // different from others.
   Config->WarnMissingEntry =
       (!Config->Entry.empty() || (!Config->Shared && !Config->Relocatable));

lld/ELF/Options.td

 defm print_gc_sections: B<"print-gc-sections",
     "List removed unused sections",
     "Do not list removed unused sections (default)">;
 
 defm print_icf_sections: B<"print-icf-sections",
     "List identical folded sections",
     "Do not list identical folded sections (default)">;
 
+defm print_symbol_order:
+  Eq<"print-symbol-order", "Print symbols ordered by --call-graph-orderfile into <File>.">;
+  
 def pop_state: F<"pop-state">,
   HelpText<"Undo the effect of -push-state">;
 
 def push_state: F<"push-state">,
   HelpText<"Save the current state of -as-needed, -static and -whole-archive">;
 
 def print_map: F<"print-map">,
   HelpText<"Print a link map to the standard output">;

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 --print-symbol-order=%t3
+# RUN: FileCheck %s --input-file %t3
+
+# CHECK: B
+# CHECK-NEXT: C
+# CHECK-NEXT: D
+# CHECK-NEXT: A
+
+.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
+
+
+