Index: tools/llvm-xray/CMakeLists.txt =================================================================== --- tools/llvm-xray/CMakeLists.txt +++ tools/llvm-xray/CMakeLists.txt @@ -12,6 +12,7 @@ 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}) Index: tools/llvm-xray/xray-graph.h =================================================================== --- /dev/null +++ tools/llvm-xray/xray-graph.h @@ -0,0 +1,85 @@ +//===-- 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 +#include + +#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> 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 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> 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 Index: tools/llvm-xray/xray-graph.cc =================================================================== --- /dev/null +++ tools/llvm-xray/xray-graph.cc @@ -0,0 +1,206 @@ +//===-- 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 +#include +#include +#include + +#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 GraphInput(cl::Positional, + cl::desc(""), + cl::Required, cl::sub(Graph)); + +enum class GraphInputFormats { RAW, YAML }; +static cl::opt 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 + 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 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 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( + 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 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( + 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( + 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( + Twine("Failed accounting function calls in file '") + GraphInput + + "'.", + std::make_error_code(std::errc::bad_message)); + } + } + + GR.exportGraphAsDOT(OS); + return Error::success(); +}); +} +}