Initial work on the XRay Graph tool.

[varno]

Summary

[XRay] Implement the llvm-xray graph subcommand

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.

[dblaikie]

tools/llvm-xray/xray-graph.cc

85–89

could potentially use a conditional operator inside the [] since the expression is otherwise identical.

Also, the outer () aren't necessary - but you can keep them if you find they enhance readability.

90–92

Consider dropping {} on single line blocks.

117–121

Inconsistent bracing (why does the inner loop have braces but the outer loop doesn't? - personally I'd probably drop them from both, but I could see an argument for adding them to both - just doesn't seem right to add them only to one and not the other)

121

Extra semicolon

129

Extra semi

133–134

Drop these (it's just a static variable in this scope anyway)

175–184

Should be some common utility for this, so every tool doesn't have to go through the same hoops (probably coalesce all the instrumentation map extractor stuff as well)

tools/llvm-xray/xray-graph.h

31

No need for the explicit 'private' as it's implied/the default here.

42

(Consider LLVM's data structures - can be more memory efficient than the allocation-per-node of standard containers.

Also a map of maps might be more efficient as a map of pair -> value, if it's equivalent for your use case)

60

(similarly, consider other data structures - but also maybe consider multimap rather than map to vector)

69

Extra semicolon

[varno]

• Initial work on the XRay Graph tool.
• Responses to Phabricator comments

[varno]

Remove spurious files by basing patch on D24377

[dberris]

tools/llvm-xray/CMakeLists.txt

16

nit: we try to somewhat keep this in lexicographical order.

tools/llvm-xray/xray-graph.cc

175–184

+1 -- if you rebase again to the latest of D24377 you can use the utility function that determines the supported loader function here.

tools/llvm-xray/xray-graph.h

42

http://llvm.org/docs/ProgrammersManual.html is a good resource to look up available data structures -- for instance, for map-like containers:

http://llvm.org/docs/ProgrammersManual.html#map-like-containers-std-map-densemap-etc

You have a few choices you can work with.

[varno]

tools/llvm-xray/xray-graph.cc

175–184

Yeah there probably should be. Not yet though AFAIK.

tools/llvm-xray/xray-graph.h

42

Thinking more on this before I make changes.

60

Thinking on this more before I make changes.

[varno]

I am planning changes

[varno]

• Additional Changes in response to dblaikie's comments
• Rebase to current version of D24377 and use getSupportedLoader

[varno]

I have addressed the last open comments.

[dberris]

Cool -- now let's see some tests for this, to make sure that we don't regress it when it goes in. You can find examples of tests in the test/tools/llvm-xray/ directory.

[dberris]

Needs tests.

[varno]

• Extra work making the xray-graph tool more powerful.
• Further work on options in llvm-xray graph subcommand
• Created Tests

[dberris]

Some style comments.

As for tests I think this is an OK set for first tests, but it'd be good to look at error conditions and making sure we're handling those appropriately.

tools/llvm-xray/xray-graph.cc

122

Can you use .emplace_back(...) instead here?

156–157

Please add an empty line between the end of function definitions, and the start of the next function.

tools/llvm-xray/xray-graph.h

28–29

Please add an empty line between last non-comment and first comment lines.

76

Can you use a SmallVector<...> instead of a std::vector<...>?

116–125

Can this not happen incrementally, as we're adding the records, or on demand when we export? i.e. why do they need to be public functions?

127–128

Does this need to be part of the class? Could this not be a function in the implementation?

[varno]

tools/llvm-xray/xray-graph.cc

122

No.

tools/llvm-xray/xray-graph.h

116–125

Not really, all the records need to be added before we calculate the statistics. And I was wanting the statistics calculated to do graph transformations later (before output).

127–128

I suppose it could be a friend function, it uses private types (the TimeStat type).

[varno]

• Reply to dberris comments.

[dberris]

The formatting changes I suspect can be automated away by using clang-format, so we don't have to spend too many cycles just getting those things "right". :)

tools/llvm-xray/xray-graph.cc

175–176

Empty line between these two lines?

188–197

The indentation here is a little weird. Fix?

tools/llvm-xray/xray-graph.h

116–125

Sure, but why aren't these just implementation details of the exportGraphAsDOT(...) function?

127–128

It doesn't have to use that type, right? I suspect you could just make this a template in the unnamed namespace in the implementation. Or that type could just be public and you could just use it (i.e for example you might want to be able to provide an iterator to the graph later, so that other commands can leverage the graph too).

[varno]

• Comments by Dberris

[varno]

tools/llvm-xray/xray-graph.h

116–125

I suppose that right now they could be, but I have plans that require them to be run before exportGraphAsDOT

[dberris]

Did you run this through clang-format in LLVM mode?

tools/llvm-xray/xray-graph.cc

230–231

Missing empty line between these two.

345–348

I'm looking at these lines and thinking it seems they're unnecessarily exposing implementation details -- really these things are something the graph renderer can decide itself if it took the file header as an argument to the constructor. And these really ought to just happen when we're exporting the data as DOT and passing arguments to the kind of data we want to see.

tools/llvm-xray/xray-graph.h

116–125

I suspect we can break these out later if we really need to. For now, they're a distraction and from an API design perspective, really brittle -- if someone wants to use this class they have to know to call these functions before exporting. If this doesn't happen while we're accounting the records, then this means the state of the graph is not easily determined.

If for example an external algorithm requires the graph, then we ought to be able to access the graph itself -- and maybe the accounting ought to happen externally instead, as an algorithm that passes through the graph we've built or as an extension to the graph traversal algorithm being employed, exposed as a method to this class.

[varno]

• Replying to comments

[varno]

tools/llvm-xray/xray-graph.h

116–125

Ok, I'll break them out and we can add them in later if needed

[dberris]

tools/llvm-xray/xray-graph.h

44–45

Missing empty line between these two.

75–76

Missing line in between these two.

[varno]

• Patch comment reply

[dberris]

Now had a look closely at the implementation. Please pardon the piecemeal review.

tools/llvm-xray/xray-graph.cc

103

Potentially spurious empty line here.

118

Also potentially spurious empty line here.

143–149

So I think in a future change which we talked about offline, we ought to make this and the account tool work with each other in some form of refactored implementation -- where the account tool can depend on the graph tool instead of duplicating a lot of this logic.

If you rebase against the account change (D24377) then the version used there now has less calls to .pop_back() on the vector, and also has a simpler loop as a result (i.e. you don't need the extra spillover logic, and the version there has less nesting and more straight-line code anyway.

The actionable comment right now I think would be a //FIXME: Refactor this and the account subcommand to reduce code duplication

151

Maybe use a name that isn't overloaded in this context -- D is a perfectly fine letter for something that indicates the delta between two numbers.

205–206

Empty line in between, and don't need void in the function arguments.

215

No need for void in the function arguments.

216

Consider also using a SmallVector here, with potentially the same initial size as with the adjacency list we maintain.

222

It's thoroughly confusing too that you're using Timings here, but there's a data member named Timings as well. :)

222–229

Is there no way to do this in a single pass, in the same loop above? I could imagine building a map that contains a vertex as the key, then accumulating statistics as you go traversing the graph (or even just storing the data anyway like you do here for the timings), and another pass to collapse that data.

tools/llvm-xray/xray-graph.h

89

Why are the iterators not the same type?

93

No need for void in the function arguments.

[varno]

• Comments

[varno]

tools/llvm-xray/xray-graph.cc

222–229

Really not, the way here has linear space and uses the required memory for each section. If we did not care about memory I could store the accumulation data for both edges and vertices. but otherwise ???

[varno]

• Reply to dberris comments.
• Comments
• comments

[dberris]

From a style perspective and implementation I think this is mostly OK -- waiting on @dblaikie to have a look.

tools/llvm-xray/xray-graph.cc

222–229

Right, so the alternate body of the function seems to be more straight-forward, and the amount of memory being used isn't that bad. You can even be smart about this and have an upper bound on the elements in the vector, and as you insert you keep a relative order and track median, and other percentiles incrementally. That's not as critical as the functionality though, and we can tune this as we go along late anyway if we encounter really big graphs in practice that would cause this to be a huge problem (either as implemented or even in the alternative version).

I'm happy either way if you choose to stick with the current implementation, but if you do consider just removing the alternate implementation you have here #ifdef 0'd out.

[dblaikie]

test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml

8–17 ↗

(On Diff #80696)

This seems to be passing a variety of values for '-e' but tests that the behavior is the same in all of them. I'm assuming the flag does something - do you have tests that confirm that it does the right thing? (somewhat similar for the top two test cases too)

39–40 ↗

(On Diff #80696)

Is deduce-sibling-calls tested?

tools/llvm-xray/xray-graph.cc

212–213

Is this optimization worthwhile? Or could we put this as a local variable in the outer loop below - no need to clear it, etc.

223

Remove dead code

288–289

Probably skip the extra language like "does what the name suggests" and "does this in the expected way".

If it's pretty obvious/self explanatory, then a brief comment is OK.

341–342

Should this be silently handled? If a user specifies a file, seems like we should error if it's not there

(@dberris - goes for existing tools too, I imagine, guess I didn't notice this in the others)

359

Move this to where it's used (then you could even use 'const auto *' if you like

[varno]

test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml

8–17 ↗

(On Diff #80696)

I need to add additional test cases for these, however the test case size for -e 99p must be quite long in order for it to work. Will add in next revision of patch.

39–40 ↗

(On Diff #80696)

Yes. Otherwise the graph would only have two nodes with timing information

tools/llvm-xray/xray-graph.cc

212–213

I think it is worth while, however I have no testing results. At this time, as I am working on a patch which changes how this code works completely due to a new data structure, I don't know.

[dberris]

test/tools/llvm-xray/X86/graph-simple-case.yaml

34–35 ↗

(On Diff #80696)

Did you need to write "DAG" here somewhere too?

tools/llvm-xray/CMakeLists.txt

14

Rebasing this to tip of trunk now that 'llvm-xray account' has landed might mean this dependency goes away now.

tools/llvm-xray/xray-graph.cc

212–213

I'd urge you to not change this patch, but instead stack one on top of it instead for any further changes you'd need to do. I'd much rather do that review of the refactoring separately than doing this review over with new data structures.

341–342

I think we at least should print something to the effect of "well, we can't symbolise properly". I'm happy with making this an explicit error, to not give users potentially misleading results.

359

Given the changes that have landed now, there's a better way of doing this (if we look at what's happening in llvm-xray account at least).

[varno]

Rebase and addess comment.

[varno]

test/tools/llvm-xray/X86/graph-simple-case.yaml

34–35 ↗

(On Diff #80696)

I don't need DAG here as there is only one edge in this graph.

[dberris]

test/tools/llvm-xray/X86/graph-simple-case.yaml

34–35 ↗

(On Diff #80696)

So as written, this will mean that if these lines are not arranged in exactly this order, the test will pass. If you meant to preserve order of the output lines being checked, you pick either -DAG: or -NEXT:.

This means, instead of:

#EMPTY:
#EMPTY:
#EMPTY:

It ought to be:

#EMPTY:
#EMPTY-NEXT:
#EMPTY-NEXT:
#EMPTY-NEXT:

to preserve the order of lines and matching.

[varno]

• Initial work on the XRay Graph tool.
• clang-format

[varno]

• fix tests

[varno]

Hi dblakie, I was wondering if you could land this patch for me?

[labath]

Please try to avoid adding pid_t references. This type is not available on windows. llvm::sys::ProcessInfo::ProcessId is a possible replacement (i've fixed the usage in this commit in r292206).

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 {
+  /// 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: {
+    ++ Graph[(ThreadStack.empty() ? 0 : 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";
+}
+
+// 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();
+});