[llvm] Intoduce llvm-orderfile

[serge-sans-paille]

Summary

This tool is solely meant to decypher the output of

clang -forder-file-instrumentation -mllvm -orderfile-write-mapping=mapping

Which is meant to be used to generate order file but used an
undocumented (yet simple!) format.

[serge-sans-paille]

@reviewers: I plan to add documentation once the core is validated :-)

[davidxl]

With the new ordering feature in place, do we need further development on this?

[ellis]

I'm happy to see that there is interest in order files! Recently, I've been developing order file generation within IRPGO that is understood by the llvm-profdata tool. In short, you can instrument a binary to get function traces, merge them into a profile, and then use the llvm-profdata tool to compute a function order which you can pass to the linker using -symbol-ordering-file.

$ clang -fprofile-generate -mllvm -pgo-temporal-instrumentation main.cpp
$ ./a.out
$ llvm-profdata merge default.profraw -o default.profdata
$ llvm-profdata order default.profdata -o order.txt

Please see https://discourse.llvm.org/t/rfc-temporal-profiling-extension-for-irpgo/68068 for details on that.

When combined with Lightweight Instrumentation, this is more lightweight (at runtime), has better infra support, has more features, and should give better performance than -forder-file-instrumentation. In fact, I plan to deprecate -forder-file-instrumentation now that the initial work on temporal instrumentation is done.

Please don't hesitate to reach out on discord or discourse if you have questions :)

[serge-sans-paille]

In D152722#4419875, @ellis wrote:

I'm happy to see that there is interest in order files! Recently, I've been developing order file generation within IRPGO that is understood by the llvm-profdata tool. In short, you can instrument a binary to get function traces, merge them into a profile, and then use the llvm-profdata tool to compute a function order which you can pass to the linker using -symbol-ordering-file.

$ clang -fprofile-generate -mllvm -pgo-temporal-instrumentation main.cpp
$ ./a.out
$ llvm-profdata merge default.profraw -o default.profdata
$ llvm-profdata order default.profdata -o order.txt

Please see https://discourse.llvm.org/t/rfc-temporal-profiling-extension-for-irpgo/68068 for details on that.

When combined with Lightweight Instrumentation, this is more lightweight (at runtime), has better infra support, has more features, and should give better performance than -forder-file-instrumentation. In fact, I plan to deprecate -forder-file-instrumentation now that the initial work on temporal instrumentation is done.

Please don't hesitate to reach out on discord or discourse if you have questions :)

Great news! Easier integration is a big plus for me, I definitively don't mind moving to this approach if we plan to obsolete -forder-file-instrumentation. One question though: from a user perspective, it would be great to have the ordering be transparent for the user so that any PGO build (with temporal instrumentation) would benefit from it. Does that make sense to you?

[ellis]

In D152722#4423838, @serge-sans-paille wrote:

In D152722#4419875, @ellis wrote:

I'm happy to see that there is interest in order files! Recently, I've been developing order file generation within IRPGO that is understood by the llvm-profdata tool. In short, you can instrument a binary to get function traces, merge them into a profile, and then use the llvm-profdata tool to compute a function order which you can pass to the linker using -symbol-ordering-file.

$ clang -fprofile-generate -mllvm -pgo-temporal-instrumentation main.cpp
$ ./a.out
$ llvm-profdata merge default.profraw -o default.profdata
$ llvm-profdata order default.profdata -o order.txt

Please see https://discourse.llvm.org/t/rfc-temporal-profiling-extension-for-irpgo/68068 for details on that.

When combined with Lightweight Instrumentation, this is more lightweight (at runtime), has better infra support, has more features, and should give better performance than -forder-file-instrumentation. In fact, I plan to deprecate -forder-file-instrumentation now that the initial work on temporal instrumentation is done.

Please don't hesitate to reach out on discord or discourse if you have questions :)

Great news! Easier integration is a big plus for me, I definitively don't mind moving to this approach if we plan to obsolete -forder-file-instrumentation. One question though: from a user perspective, it would be great to have the ordering be transparent for the user so that any PGO build (with temporal instrumentation) would benefit from it. Does that make sense to you?

I'm not exactly sure what you mean. Right now we need to manually pass the order file to the linker via -symbol-ordering-file, but eventually I'd like this to happen automatically when you pass the profile to the compiler via -fprofile-use=default.profdata.

llvm/test/tools/llvm-orderfile/help.test

+RUN: llvm-orderfile --help 2>&1 | FileCheck %s
+CHECK: Generic Options:
+CHECK: llvm-orderfile Options:

llvm/test/tools/llvm-orderfile/mapping.data

+MD5 b84cbfeff0d303b4 too
+MD5 786da535fe6cbd2 zoo
+MD5 db956436e78dd5fa main
+MD5 b84cbfeff0d303b4 too
+MD5 786da535fe6cbd2 zoo
+MD5 db956436e78dd5fa main

llvm/test/tools/llvm-orderfile/read.test

+RUN: llvm-orderfile %S/order.data %S/mapping.data 2>&1 | FileCheck %s
+CHECK: main
+CHECK-NEXT: zoo
+CHECK-NEXT: too

llvm/tools/llvm-orderfile/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_llvm_tool(llvm-orderfile
+  llvm-orderfile.cpp
+  )

llvm/tools/llvm-orderfile/llvm-orderfile.cpp

+//===- llvm-cat.cpp - LLVM module concatenation utility -------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This program is for testing features that rely on multi-module bitcode files.
+// It takes a list of input modules and uses them to create a multi-module
+// bitcode file.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <cstring>
+
+using namespace llvm;
+
+cl::OptionCategory OrderfileCategory("llvm-orderfile Options");
+
+static cl::opt<std::string> OutputFilename("o",
+                                           cl::desc("Output filename"),
+                                           cl::value_desc("filename"),
+                                           cl::cat(OrderfileCategory));
+
+static cl::opt<std::string> BinaryOrderFile(cl::Positional,
+                                            cl::desc("<order file>"),
+                                            cl::cat(OrderfileCategory));
+
+static cl::opt<std::string> MappingFile(cl::Positional,
+                                        cl::desc("<mapping file>"),
+                                        cl::cat(OrderfileCategory));
+
+static cl::opt<bool> Verbose("v", cl::desc("verbose output"),
+                                  cl::cat(OrderfileCategory));
+
+
+static void DumpOrderFile(MemoryBuffer& BO, DenseMap<uint64_t, StringRef> const& Mapping, raw_ostream & OS)
+{
+  StringRef BinaryOrder = BO.getBuffer();
+  constexpr size_t BinaryOrderElementSize = 8;
+  for(size_t i = 0; i < BinaryOrder.size(); i += BinaryOrderElementSize) {
+    uint64_t Elt;
+    StringRef HexElt = BinaryOrder.substr(i, BinaryOrderElementSize);
+    std::memcpy(&Elt, HexElt.data(), sizeof(Elt));
+    auto Where = Mapping.find(Elt);
+    if (Where != Mapping.end())
+      OS << Where->second << "\n";
+    else if (Verbose && Elt) {
+      llvm::errs() << "no mapping found for entry ";
+      llvm::errs().write_hex(Elt);
+      llvm::errs() << "\n";
+    }
+  }
+}
+
+
+int main(int argc, char **argv) {
+  cl::HideUnrelatedOptions(OrderfileCategory);
+  cl::ParseCommandLineOptions(argc, argv, "Orderfile manipulation");
+
+  ExitOnError ExitOnErr("llvm-orderfile: ");
+
+  std::unique_ptr<MemoryBuffer> MF = ExitOnErr(
+      errorOrToExpected(MemoryBuffer::getFileOrSTDIN(MappingFile)));
+
+  StringRef MappingStream(MF->getBuffer());
+  SmallVector<StringRef> MappingLines;
+  MappingStream.split(MappingLines, /*Separator=*/'\n', /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+
+  DenseMap<uint64_t, StringRef> Mapping;
+  SmallVector<StringRef> Tokens;
+  for(unsigned LineIndex = 0; LineIndex < MappingLines.size(); ++LineIndex) {
+    StringRef Line = MappingLines[LineIndex];
+    Line.split(Tokens, /*Separator=*/' ');
+    if (Tokens.size() != 3) {
+      llvm::errs() << MappingFile << ':' << (1 + LineIndex) << ": has invalid format\n";
+      llvm::errs() << "when parsing: " << Line << "\n";
+      return 1;
+    }
+    uint64_t Val;
+    Tokens[1].getAsInteger(16, Val);
+    Mapping[Val] = Tokens[2];
+    Tokens.clear();
+  }
+
+  if(Verbose)
+    llvm::errs() << "Found " << Mapping.size() << " mappings.\n";
+
+  std::unique_ptr<MemoryBuffer> BO = ExitOnErr(
+      errorOrToExpected(MemoryBuffer::getFile(BinaryOrderFile)));
+
+  if (OutputFilename.empty()) {
+    DumpOrderFile(*BO, Mapping, llvm::outs());
+  }
+  else {
+    std::error_code EC;
+    raw_fd_ostream OS(OutputFilename, EC, sys::fs::OpenFlags::OF_None);
+    if (EC) {
+      errs() << argv[0] << ": cannot open " << OutputFilename << " for writing: "
+             << EC.message();
+      return 1;
+    }
+    DumpOrderFile(*BO, Mapping, OS);
+  }
+
+
+  return 0;
+}