[XRay] Implement the `llvm-xray graph` subcommand

[varno]

Summary

This is an innitial change to implement a new subcommand for the llvm-xray tool.

Here we define the graph subcommand which generates a graph from the function
call information and uses it to present the call information graphically with
additional annotations. This tool was originally proposed by dberris.

Depends on D24377.

[varno]

Changed diff base from master to D24377.

[varno]

Adding Reviewers as recommended by dberris.

[varno]

Trying again

tools/llvm-xray/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   DebugInfoDWARF
   Object
   Support
   Symbolize)
 
 set(LLVM_XRAY_TOOLS
   func-id-helper.cc
   xray-account.cc
   xray-converter.cc
   xray-extract.cc
   xray-extract.cc
   xray-log-reader.cc
-  xray-registry.cc)
+  xray-registry.cc
+  xray-graph.cc)
 
 add_llvm_tool(llvm-xray llvm-xray.cc ${LLVM_XRAY_TOOLS})

tools/llvm-xray/xray-graph.h

+//===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Generate a DOT file to represent the function call graph encountered in
+// the trace.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef XRAY_GRAPH_H
+#define XRAY_GRAPH_H
+
+#include <unordered_map>
+#include <vector>
+
+#include "func-id-helper.h"
+#include "xray-record.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+namespace xray {
+/// A class encapsulating the logic related to analyzing XRay traces, producting
+/// Graphs from them and then exporting those graphs for review.
+class GraphRenderer {
+private:
+  /// An inner struct for storing edge attributes for our graph. Here the
+  /// attributes are mainly function call statistics.
+  ///
+  /// FIXME: expand to contain more information eg call latencies.
+  struct EdgeAttribute {
+    uint64_t CallCount = 0;
+  };
+
+  /// The Graph stored in an edge-list like format, with the edges also having
+  /// An attached set of attributes.
+  std::unordered_map<int32_t, std::unordered_map<int32_t, EdgeAttribute>> Graph;
+
+  /// An Inner Struct for storing vertex attributes, at the moment just
+  /// SymbolNames, however in future we could store bulk function statistics.
+  ///
+  /// FIXME: Store more attributes based on instrumentation map.
+  struct VertexAttribute {
+    std::string SymbolName;
+  };
+
+  /// Graph Vertex Attributes. These are presently stored seperate from the
+  /// main graph.
+  std::unordered_map<int32_t, VertexAttribute> VertexAttrs;
+
+  /// Use a Map to store the Function stack for each thread whilst building the
+  /// graph.
+  ///
+  /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
+  std::unordered_map<pid_t, std::vector<int32_t>> PerThreadFunctionStack;
+
+  /// Usefull object for getting human readable Symbol Names.
+  FuncIdConversionHelper &FuncIdHelper;
+
+public:
+  /// Takes in a reference to a FuncIdHelper in order to have ready access to
+  /// Symbol names.
+  explicit GraphRenderer(FuncIdConversionHelper &FuncIdHelper)
+      : FuncIdHelper(FuncIdHelper){};
+
+  /// Process an Xray record and expand the graph.
+  ///
+  /// This Function will return true on success, or false if records are not
+  /// presented in per-thread call-tree DFS order. (That is for each thread the
+  /// Records should be in order runtime on an ideal system.)
+  ///
+  /// FIXME: Make this more robust against small irregularities.
+  bool accountRecord(const XRayRecord &Record);
+
+  /// Output the Embedded graph in DOT format on \p OS.
+  void exportGraphAsDOT(raw_ostream &OS) const;
+};
+}
+}
+
+#endif // XRAY_GRAPH_H

tools/llvm-xray/xray-graph.cc

+//===-- xray-graph.c - XRay Function Call Graph Renderer ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Generate a DOT file to represent the function call graph encountered in
+// the trace.
+//
+//===----------------------------------------------------------------------===//
+#include <algorithm>
+#include <cassert>
+#include <system_error>
+#include <utility>
+
+#include "xray-extract.h"
+#include "xray-graph.h"
+#include "xray-log-reader.h"
+#include "xray-registry.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/FormatVariadic.h"
+
+using namespace llvm;
+using namespace xray;
+
+// Setup llvm-xray graph subcommand and its options.
+static cl::SubCommand Graph("graph", "Generate function-call graph");
+static cl::opt<std::string> GraphInput(cl::Positional,
+                                       cl::desc("<xray log file>"),
+                                       cl::Required, cl::sub(Graph));
+
+enum class GraphInputFormats { RAW, YAML };
+static cl::opt<GraphInputFormats> GraphInputFormat(
+    "input-format", cl::desc("input format"),
+    cl::values(clEnumValN(GraphInputFormats::RAW, "binary", "input in binary"),
+               clEnumValN(GraphInputFormats::YAML, "yaml", "input in yaml")),
+    cl::sub(Graph));
+static cl::alias GraphInputFormat2("i", cl::desc("Alias for -input-format"),
+                                   cl::aliasopt(GraphInputFormat),
+                                   cl::sub(Graph));
+
+static cl::opt<std::string>
+    GraphOutput("output", cl::value_desc("Output file"), cl::init("-"),
+                cl::desc("output file; use '-' for stdout"), cl::sub(Graph));
+static cl::alias GraphOutput2("o", cl::aliasopt(GraphOutput),
+                              cl::desc("Alias for -output"), cl::sub(Graph));
+
+static cl::opt<std::string> GraphInstrMap(
+    "instr_map", cl::desc("binary with the instrumrntation map, or "
+                          "a separate instrumentation map"),
+    cl::value_desc("binary with xray_instr_map"), cl::sub(Graph), cl::init(""));
+static cl::alias GraphInstrMap2("m", cl::aliasopt(GraphInstrMap),
+                                cl::desc("alias for -instr_map"),
+                                cl::sub(Graph));
+
+static cl::opt<InstrumentationMapExtractor::InputFormats> InstrMapFormat(
+    "instr-map-format", cl::desc("format of instrumentation map"),
+    cl::values(clEnumValN(InstrumentationMapExtractor::InputFormats::ELF, "elf",
+                          "instrumentation map in an ELF header"),
+               clEnumValN(InstrumentationMapExtractor::InputFormats::YAML,
+                          "yaml", "instrumentation map in YAML")),
+    cl::sub(Graph), cl::init(InstrumentationMapExtractor::InputFormats::ELF));
+static cl::alias InstrMapFormat2("t", cl::aliasopt(InstrMapFormat),
+                                 cl::desc("Alias for -instr-map-format"),
+                                 cl::sub(Graph));
+
+// Evaluates an XRay record and performs accounting on it, creating and
+// decorating a function call graph as it does so. It does this by maintaining
+// a call stack on a per-thread basis and adding edges and verticies to the
+// graph as they are seen for the first time.
+//
+// There is an immaginary root for functions at the top of their stack with
+// FuncId 0.
+//
+// FIXME: make more robust to errors and
+// Decorate Graph More Heavily.
+bool GraphRenderer::accountRecord(const XRayRecord &Record) {
+  auto &ThreadStack = PerThreadFunctionStack[Record.TId];
+  switch (Record.Type) {
+  case RecordTypes::ENTER: {
+    if (ThreadStack.size() == 0) {
+      ++(Graph[0][Record.FuncId].CallCount);
+    } else {
+      ++(Graph[ThreadStack.back()][Record.FuncId].CallCount);
+    }
+    if (VertexAttrs.count(Record.FuncId) == 0) {
+      VertexAttrs[Record.FuncId] = {FuncIdHelper.SymbolOrNumber(Record.FuncId)};
+    }
+    ThreadStack.push_back(Record.FuncId);
+    break;
+  }
+  case RecordTypes::EXIT: {
+    if (ThreadStack.size() == 0 || ThreadStack.back() != Record.FuncId)
+      return false;
+
+    ThreadStack.pop_back();
+    break;
+  }
+  }
+
+  return true;
+}
+
+// Does what the name suggests, it creates a DOT file from the Graph embedded in
+// the GraphRenderer object. It does this in the expected way by itterating
+// through all edges then vertices and then outputting them and their
+// annotations.
+//
+// FIXME: output more information, better presented.
+void GraphRenderer::exportGraphAsDOT(raw_ostream &OS) const {
+  OS << "digraph xray {\n";
+
+  for (const auto &V : Graph)
+    for (const auto &E : V.second) {
+      OS << "F" << V.first << " -> "
+         << "F" << E.first << " label=\"" << E.second.CallCount << "\"];\n";
+    };
+
+  for (const auto &V : VertexAttrs) {
+    OS << "F" << V.first << " [label=\""
+       << (V.second.SymbolName.size() > 40
+               ? V.second.SymbolName.substr(0, 40) + "..."
+               : V.second.SymbolName)
+       << "\"];\n";
+  };
+  OS << "}\n";
+}
+
+namespace llvm {
+namespace xray {
+
+// Here we register and implement the llvm-xray graph subcommand.
+// The bulk of this code reads in the options, opens the required files, uses
+// those files to create a context for analysing the xray trace, then there is a
+// short loop which actually analyses the trace, generates the graph and then
+// outputs it as a DOT.
+//
+// FIXME: include additional filtering and annalysis passes to provide more
+// specific useful information.
+static CommandRegistration Unused(&Graph, []() -> Error {
+  int Fd;
+  auto EC = sys::fs::openFileForRead(GraphInput, Fd);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + GraphInput + "'", EC);
+
+  Error Err = Error::success();
+  xray::InstrumentationMapExtractor Extractor(GraphInstrMap, InstrMapFormat,
+                                              Err);
+  if (auto E = handleErrors(
+          std::move(Err), [&](std::unique_ptr<StringError> E) -> Error {
+            if (E->convertToErrorCode() == std::errc::no_such_file_or_directory)
+              return Error::success();
+            return Error(std::move(E));
+          }))
+    return E;
+
+  raw_fd_ostream OS(GraphOutput, EC, sys::fs::OpenFlags::F_Text);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + GraphOutput + "' for writing.", EC);
+
+  const auto &FunctionAddresses = Extractor.getFunctionAddresses();
+  symbolize::LLVMSymbolizer::Options Opts(
+      symbolize::FunctionNameKind::LinkageName, true, true, false, "");
+  symbolize::LLVMSymbolizer Symbolizer(Opts);
+  llvm::xray::FuncIdConversionHelper FuncIdHelper(GraphInstrMap, Symbolizer,
+                                                  FunctionAddresses);
+  xray::GraphRenderer GR(FuncIdHelper);
+
+  LogReader::LoaderFunction Loader;
+  switch (GraphInputFormat) {
+  case GraphInputFormats::RAW:
+    Loader = NaiveLogLoader;
+    break;
+  case GraphInputFormats::YAML:
+    Loader = YAMLLogLoader;
+    break;
+  };
+
+  LogReader Reader(GraphInput, Err, true, Loader);
+  if (Err)
+    return joinErrors(
+        make_error<StringError>(
+            Twine("Failed loading input file '") + GraphInput + "'",
+            std::make_error_code(std::errc::protocol_error)),
+        std::move(Err));
+
+  for (const auto &Record : Reader) {
+    // Generate graph, FIXME: better error recovery.
+    if (!GR.accountRecord(Record)) {
+      return make_error<StringError>(
+          Twine("Failed accounting function calls in file '") + GraphInput +
+              "'.",
+          std::make_error_code(std::errc::bad_message));
+    }
+  }
+
+  GR.exportGraphAsDOT(OS);
+  return Error::success();
+});
+}
+}