[XRay][llvm] Load XRay Profiles

[dberris]

Summary

This change implements the profile loading functionality in LLVM to
support XRay's profiling mode in compiler-rt.

We introduce a type named llvm::xray::Profile which allows building a
profile representation. We can load an XRay profile from a file to build
Profile instances, or do it manually through the Profile type's API.

The intent is to get the llvm-xray tool to generate Profile
instances and use that as the common abstraction through which all
conversion and analysis can be done. In the future we can generate
Profile instances from Trace instances as well, through conversion
functions.

Some of the key operations supported by the Profile API are:

• Path interning (Profile::internPath(...)) which returns a unique path identifier.

• Block appending (Profile::addBlock(...)) to add thread-associated profile information.

• Path ID to Path lookup (Profile::expandPath(...)) to look up a PathID and return the original interned path.

• Block iteration.

A 'Path' in this context represents the function call stack in
leaf-to-root order. This is represented as a path in an internally
managed prefix tree in the Profile instance. Having a handle (PathID)
to identify the unique Paths we encounter for a particular Profile
allows us to reduce the amount of memory required to associate profile
data to a particular Path.

This is the first of a series of patches to migrate the llvm-stacks
tool towards using a single profile representation.

Depends on D48653.

[dberris]

• fixup: Implement Profile merging

[dberris]

Rebase, update description.

[kpw]

Is this still a work in progress patch as noted? I'll make some time to look at this today.

[dberris]

In D48370#1157578, @kpw wrote:

Is this still a work in progress patch as noted? I'll make some time to look at this today.

Yes, still in progress. However we can start making progress on issues with the current state if you find any.

I suspect we can land changes on this incrementally, but I'd at least like to get to a point where we can convert Trace objects to Profile objects. That's next on my list of things to do, so that we can use the Profile type in the llvm-xray stacks tool at least.

Thoughts?

[kpw]

Publishing existing comments. Haven't reviewed the whole patch.

llvm/include/llvm/XRay/Profile.h

55–56 ↗

(On Diff #154161)

Maybe call this expand and elaborate on what type of error conditions are possible. Is the Expected just for an invalid id?

59 ↗

(On Diff #154161)

What happens when a caller provides an argument that has already been interned? Will they receive a new ID or the existing one?

62 ↗

(On Diff #154161)

The header should document the error cases. Is it intended semantics to add a block that has a ThreadId and a PathId pair that already exist in another block? Will this accumulate the call count and cumulative time for the path? What about cases where some of the PathIds in the block have been interned and some haven't. Is there partial success?

[dberris]

• fixup: Handle profile loading better in llvm-xray
• fixup: profileFromTrace(Trace) -> Expected<Profile>
• fixup: Update some comments
• fixup: FIXME markers, additional tests, rename path to expandPath

[dberris]

llvm/include/llvm/XRay/Profile.h

55–56 ↗

(On Diff #154161)

Yes, error is for an unknown PathID -- called it expandPath instead.

59 ↗

(On Diff #154161)

Interning implies that it will return the same ID for the same path. This is very similar to string interning. I've made that a bit more explicit in the comment.

[dberris]

Reduced the scope of the patch. We'll work on follow-on changes to implement more of the functionality, working towards moving more of the implementation in llvm-stacks to libraries.

[kpw]

Haven't read the test yet. Logic looks sound.

llvm/include/llvm/XRay/Profile.h

38 ↗

(On Diff #158175)

Do we have a better way of passing files around as streams of bytes or a DataExtractor so that we can more easily work with sockets or other data streams later?

llvm/lib/XRay/Profile.cpp

69–72 ↗

(On Diff #158175)

This pattern is repeated several times. Set the current offset, read something, check to see that the offset moved, and update the current offset. Did you think about abstracting to avoid mistakes like forgetting to update CurrentOffset?

130 ↗

(On Diff #158175)

Since this function is pretty long, it might help to call this RootToLeafPath.

187–188 ↗

(On Diff #158175)

There is a bit of the cascading auto here where the compiler is fine, but a reader might get a bit lost.

It is not too verbose and might help to make these:
Profile::PathID &PathID and
Profile::Data &Data.

194–196 ↗

(On Diff #158175)

It might be worth noting here that you intentionally disregard whether the insert added a new element.

204–208 ↗

(On Diff #158175)

Since this is the only difference between the two loops, it could make the code more simple at a small performance cost (boolean check) to simply run the same loop twice even though Inserted will always be true the first time.

222 ↗

(On Diff #158175)

Another idea for code re-use. mergeProfilesByStack and mergeProfilesByThread could both call a routine like mergeProfilesByThread but with an additional parameter that is a callable that picks out the thread id from a function. It would simply return zero for mergeProfilesByStack. The code could be identical and create a map with a single element.

If you prefer to specialize that's your call, but this is less performance critical IIUC since it's not in compiler-rt.

376 ↗

(On Diff #158175)

on Block per thread -> one Block per thread

[dberris]

Address comments by @kpw.

llvm/include/llvm/XRay/Profile.h

38 ↗

(On Diff #158175)

Ideally we'll take a DataExtractor instance. We can add that later, at this point we don't quite need it yet.

llvm/lib/XRay/Profile.cpp

69–72 ↗

(On Diff #158175)

Looks like this isn't something easily automated. :(

This is very much an artefact of the data extractor interface.

187–188 ↗

(On Diff #158175)

It actually turns out to be more cumbersome, because of the repetition of the type and the identifier being spelled the same:

const Profile::PathID &PathID = ...;
const Profile::Data &Data = ...;

194–196 ↗

(On Diff #158175)

Used std::tie(It, std::ignore) = ... instead.

222 ↗

(On Diff #158175)

The algorithms are very different, since the additional data structure for grouping by threads is by definition unnecessary in the merging across stacks losing information about threads.

[kpw]

Please consider my comments about the tests before pushing.

llvm/lib/XRay/Profile.cpp

187–188 ↗

(On Diff #158175)

In the words of the dude: "That's just like... your opinion man."

222 ↗

(On Diff #158175)

That's fair.

llvm/unittests/XRay/ProfileTest.cpp

49–56 ↗

(On Diff #158683)

Could you add a comment explaining each assertion. If these fail, the aggregate initializers require a lot from an unfamiliar reader.

Suggestions:

Empty struct should fail
...
Thread ID with no data should fail
...
// Thread ID with data should succeed

Die hard style reviewers would argue that this should be three tests! ;P

60–72 ↗

(On Diff #158683)

Maybe choose some values that are different for the different stacks so that if the test will fail if the merge combines an incorrect permutation pairing up the stacks?

Maybe also add a unique stack to one or both profiles to check that the implementation is robust to stacks that don't have a match.

101 ↗

(On Diff #158683)

Use a different thread ID here to verify we're not matching on threads?

118 ↗

(On Diff #158683)

Should there be MergeProfilesByThreadAccumulate as well?

121–127 ↗

(On Diff #158683)

Use different thread IDs?

[dberris]

Address more comments.

[dberris]

Thanks!

llvm/lib/XRay/Profile.cpp

187–188 ↗

(On Diff #158175)

Duuuuude... :)

[thakis]

(The cmakelists.txt changes added tabs. I fixed in r338880, but maybe check your editor settings. also, phab doesn't do a great job displaying tabs in diffs :-/)

[dberris]

Oops -- sorry about that, Nico!

/me goes checking editor config settings for cmake files to expand tabs always.

[dberris]

Re-opening since this has been reverted.

[dberris]

Turns out that a move-only type and how we're using this is problematic in some older non-clang compiler. Instead of relying on defaults, I'll implement the semantics that we need for copy to work even if it's much more expensive.

[dberris]

Updated to implement a copy constructor, a move constructor, and associated assignment operations.

[dberris]

• fixup: add test for move assignment

[dberris]

Updated, anybody care to review (again)?

[dberris]

Am going to land this now, since the changes introduced have been very minor (mostly to appease older compilers).

llvm/trunk/include/llvm/XRay/Profile.h

+//===- Profile.h - XRay Profile Abstraction -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the XRay Profile class representing the latency profile generated by
+// XRay's profiling mode.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_XRAY_PROFILE_H
+#define LLVM_XRAY_PROFILE_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+#include <list>
+#include <utility>
+#include <vector>
+
+namespace llvm {
+namespace xray {
+
+class Profile;
+
+// We forward declare the Trace type for turning a Trace into a Profile.
+class Trace;
+
+/// This function will attempt to load an XRay Profiling Mode profile from the
+/// provided |Filename|.
+///
+/// For any errors encountered in the loading of the profile data from
+/// |Filename|, this function will return an Error condition appropriately.
+Expected<Profile> loadProfile(StringRef Filename);
+
+/// This algorithm will merge two Profile instances into a single Profile
+/// instance, aggregating blocks by Thread ID.
+Profile mergeProfilesByThread(const Profile &L, const Profile &R);
+
+/// This algorithm will merge two Profile instances into a single Profile
+/// instance, aggregating blocks by function call stack.
+Profile mergeProfilesByStack(const Profile &L, const Profile &R);
+
+/// This function takes a Trace and creates a Profile instance from it.
+Expected<Profile> profileFromTrace(const Trace &T);
+
+/// Profile instances are thread-compatible.
+class Profile {
+public:
+  using ThreadID = uint64_t;
+  using PathID = unsigned;
+  using FuncID = int32_t;
+
+  struct Data {
+    uint64_t CallCount;
+    uint64_t CumulativeLocalTime;
+  };
+
+  struct Block {
+    ThreadID Thread;
+    std::vector<std::pair<PathID, Data>> PathData;
+  };
+
+  /// Provides a sequence of function IDs from a previously interned PathID.
+  ///
+  /// Returns an error if |P| had not been interned before into the Profile.
+  ///
+  Expected<std::vector<FuncID>> expandPath(PathID P) const;
+
+  /// The stack represented in |P| must be in stack order (leaf to root). This
+  /// will always return the same PathID for |P| that has the same sequence.
+  PathID internPath(ArrayRef<FuncID> P);
+
+  /// Appends a fully-formed Block instance into the Profile.
+  ///
+  /// Returns an error condition in the following cases:
+  ///
+  ///    - The PathData component of the Block is empty
+  ///
+  Error addBlock(Block &&B);
+
+  Profile() = default;
+  ~Profile() = default;
+
+  Profile(Profile &&O) noexcept
+      : Blocks(std::move(O.Blocks)), NodeStorage(std::move(O.NodeStorage)),
+        Roots(std::move(O.Roots)), PathIDMap(std::move(O.PathIDMap)),
+        NextID(O.NextID) {}
+
+  Profile &operator=(Profile &&O) noexcept {
+    Blocks = std::move(O.Blocks);
+    NodeStorage = std::move(O.NodeStorage);
+    Roots = std::move(O.Roots);
+    PathIDMap = std::move(O.PathIDMap);
+    NextID = O.NextID;
+    return *this;
+  }
+
+  Profile(const Profile &);
+  Profile &operator=(const Profile &);
+
+  friend void swap(Profile &L, Profile &R) {
+    using std::swap;
+    swap(L.Blocks, R.Blocks);
+    swap(L.NodeStorage, R.NodeStorage);
+    swap(L.Roots, R.Roots);
+    swap(L.PathIDMap, R.PathIDMap);
+    swap(L.NextID, R.NextID);
+  }
+
+private:
+  using BlockList = std::list<Block>;
+
+  struct TrieNode {
+    FuncID Func = 0;
+    std::vector<TrieNode *> Callees{};
+    TrieNode *Caller = nullptr;
+    PathID ID = 0;
+  };
+
+  // List of blocks associated with a Profile.
+  BlockList Blocks;
+
+  // List of TrieNode elements we've seen.
+  std::list<TrieNode> NodeStorage;
+
+  // List of call stack roots.
+  SmallVector<TrieNode *, 4> Roots;
+
+  // Reverse mapping between a PathID to a TrieNode*.
+  DenseMap<PathID, TrieNode *> PathIDMap;
+
+  // Used to identify paths.
+  PathID NextID = 1;
+
+public:
+  using const_iterator = BlockList::const_iterator;
+  const_iterator begin() const { return Blocks.begin(); }
+  const_iterator end() const { return Blocks.end(); }
+  bool empty() const { return Blocks.empty(); }
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif

llvm/trunk/lib/XRay/CMakeLists.txt

 add_llvm_library(LLVMXRay
   FileHeaderReader.cpp
   InstrumentationMap.cpp
+  Profile.cpp
   Trace.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/ADT
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/XRay
 
   DEPENDS
   LLVMSupport
   LLVMObject
 
   LINK_LIBS
   LLVMSupport
   LLVMObject
   )

llvm/trunk/lib/XRay/Profile.cpp

+//===- Profile.cpp - XRay Profile Abstraction -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the XRay Profile class representing the latency profile generated by
+// XRay's profiling mode.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/XRay/Profile.h"
+
+#include "llvm/Support/DataExtractor.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/XRay/Trace.h"
+#include <deque>
+#include <memory>
+
+namespace llvm {
+namespace xray {
+
+Profile::Profile(const Profile &O) {
+  // We need to re-create all the tries from the original (O), into the current
+  // Profile being initialized, through the Block instances we see.
+  for (const auto &Block : O) {
+    Blocks.push_back({Block.Thread, {}});
+    auto &B = Blocks.back();
+    for (const auto &PathData : Block.PathData)
+      B.PathData.push_back({internPath(cantFail(O.expandPath(PathData.first))),
+                            PathData.second});
+  }
+}
+
+Profile &Profile::operator=(const Profile &O) {
+  Profile P = O;
+  *this = std::move(P);
+  return *this;
+}
+
+namespace {
+
+struct BlockHeader {
+  uint32_t Size;
+  uint32_t Number;
+  uint64_t Thread;
+};
+
+static Expected<BlockHeader> readBlockHeader(DataExtractor &Extractor,
+                                             uint32_t &Offset) {
+  BlockHeader H;
+  uint32_t CurrentOffset = Offset;
+  H.Size = Extractor.getU32(&Offset);
+  if (Offset == CurrentOffset)
+    return make_error<StringError>(
+        Twine("Error parsing block header size at offset '") +
+            Twine(CurrentOffset) + "'",
+        std::make_error_code(std::errc::invalid_argument));
+  CurrentOffset = Offset;
+  H.Number = Extractor.getU32(&Offset);
+  if (Offset == CurrentOffset)
+    return make_error<StringError>(
+        Twine("Error parsing block header number at offset '") +
+            Twine(CurrentOffset) + "'",
+        std::make_error_code(std::errc::invalid_argument));
+  CurrentOffset = Offset;
+  H.Thread = Extractor.getU64(&Offset);
+  if (Offset == CurrentOffset)
+    return make_error<StringError>(
+        Twine("Error parsing block header thread id at offset '") +
+            Twine(CurrentOffset) + "'",
+        std::make_error_code(std::errc::invalid_argument));
+  return H;
+}
+
+static Expected<std::vector<Profile::FuncID>> readPath(DataExtractor &Extractor,
+                                                       uint32_t &Offset) {
+  // We're reading a sequence of int32_t's until we find a 0.
+  std::vector<Profile::FuncID> Path;
+  auto CurrentOffset = Offset;
+  int32_t FuncId;
+  do {
+    FuncId = Extractor.getSigned(&Offset, 4);
+    if (CurrentOffset == Offset)
+      return make_error<StringError>(
+          Twine("Error parsing path at offset '") + Twine(CurrentOffset) + "'",
+          std::make_error_code(std::errc::invalid_argument));
+    CurrentOffset = Offset;
+    Path.push_back(FuncId);
+  } while (FuncId != 0);
+  return std::move(Path);
+}
+
+static Expected<Profile::Data> readData(DataExtractor &Extractor,
+                                        uint32_t &Offset) {
+  // We expect a certain number of elements for Data:
+  //   - A 64-bit CallCount
+  //   - A 64-bit CumulativeLocalTime counter
+  Profile::Data D;
+  auto CurrentOffset = Offset;
+  D.CallCount = Extractor.getU64(&Offset);
+  if (CurrentOffset == Offset)
+    return make_error<StringError>(
+        Twine("Error parsing call counts at offset '") + Twine(CurrentOffset) +
+            "'",
+        std::make_error_code(std::errc::invalid_argument));
+  CurrentOffset = Offset;
+  D.CumulativeLocalTime = Extractor.getU64(&Offset);
+  if (CurrentOffset == Offset)
+    return make_error<StringError>(
+        Twine("Error parsing cumulative local time at offset '") +
+            Twine(CurrentOffset) + "'",
+        std::make_error_code(std::errc::invalid_argument));
+  return D;
+}
+
+} // namespace
+
+Error Profile::addBlock(Block &&B) {
+  if (B.PathData.empty())
+    return make_error<StringError>(
+        "Block may not have empty path data.",
+        std::make_error_code(std::errc::invalid_argument));
+
+  Blocks.emplace_back(std::move(B));
+  return Error::success();
+}
+
+Expected<std::vector<Profile::FuncID>> Profile::expandPath(PathID P) const {
+  auto It = PathIDMap.find(P);
+  if (It == PathIDMap.end())
+    return make_error<StringError>(
+        Twine("PathID not found: ") + Twine(P),
+        std::make_error_code(std::errc::invalid_argument));
+  std::vector<Profile::FuncID> Path;
+  for (auto Node = It->second; Node; Node = Node->Caller)
+    Path.push_back(Node->Func);
+  return std::move(Path);
+}
+
+Profile::PathID Profile::internPath(ArrayRef<FuncID> P) {
+  if (P.empty())
+    return 0;
+
+  auto RootToLeafPath = reverse(P);
+
+  // Find the root.
+  auto It = RootToLeafPath.begin();
+  auto PathRoot = *It++;
+  auto RootIt =
+      find_if(Roots, [PathRoot](TrieNode *N) { return N->Func == PathRoot; });
+
+  // If we've not seen this root before, remember it.
+  TrieNode *Node = nullptr;
+  if (RootIt == Roots.end()) {
+    NodeStorage.emplace_back();
+    Node = &NodeStorage.back();
+    Node->Func = PathRoot;
+    Roots.push_back(Node);
+  } else {
+    Node = *RootIt;
+  }
+
+  // Now traverse the path, re-creating if necessary.
+  while (It != RootToLeafPath.end()) {
+    auto NodeFuncID = *It++;
+    auto CalleeIt = find_if(Node->Callees, [NodeFuncID](TrieNode *N) {
+      return N->Func == NodeFuncID;
+    });
+    if (CalleeIt == Node->Callees.end()) {
+      NodeStorage.emplace_back();
+      auto NewNode = &NodeStorage.back();
+      NewNode->Func = NodeFuncID;
+      NewNode->Caller = Node;
+      Node->Callees.push_back(NewNode);
+      Node = NewNode;
+    } else {
+      Node = *CalleeIt;
+    }
+  }
+
+  // At this point, Node *must* be pointing at the leaf.
+  assert(Node->Func == P.front());
+  if (Node->ID == 0) {
+    Node->ID = NextID++;
+    PathIDMap.insert({Node->ID, Node});
+  }
+  return Node->ID;
+}
+
+Profile mergeProfilesByThread(const Profile &L, const Profile &R) {
+  Profile Merged;
+  using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
+  using PathDataMapPtr = std::unique_ptr<PathDataMap>;
+  using PathDataVector = decltype(Profile::Block::PathData);
+  using ThreadProfileIndexMap = DenseMap<Profile::ThreadID, PathDataMapPtr>;
+  ThreadProfileIndexMap ThreadProfileIndex;
+
+  for (const auto &P : {std::ref(L), std::ref(R)})
+    for (const auto &Block : P.get()) {
+      ThreadProfileIndexMap::iterator It;
+      std::tie(It, std::ignore) = ThreadProfileIndex.insert(
+          {Block.Thread, PathDataMapPtr{new PathDataMap()}});
+      for (const auto &PathAndData : Block.PathData) {
+        auto &PathID = PathAndData.first;
+        auto &Data = PathAndData.second;
+        auto NewPathID =
+            Merged.internPath(cantFail(P.get().expandPath(PathID)));
+        PathDataMap::iterator PathDataIt;
+        bool Inserted;
+        std::tie(PathDataIt, Inserted) = It->second->insert({NewPathID, Data});
+        if (!Inserted) {
+          auto &ExistingData = PathDataIt->second;
+          ExistingData.CallCount += Data.CallCount;
+          ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
+        }
+      }
+    }
+
+  for (const auto &IndexedThreadBlock : ThreadProfileIndex) {
+    PathDataVector PathAndData;
+    PathAndData.reserve(IndexedThreadBlock.second->size());
+    copy(*IndexedThreadBlock.second, std::back_inserter(PathAndData));
+    cantFail(
+        Merged.addBlock({IndexedThreadBlock.first, std::move(PathAndData)}));
+  }
+  return Merged;
+}
+
+Profile mergeProfilesByStack(const Profile &L, const Profile &R) {
+  Profile Merged;
+  using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
+  PathDataMap PathData;
+  using PathDataVector = decltype(Profile::Block::PathData);
+  for (const auto &P : {std::ref(L), std::ref(R)})
+    for (const auto &Block : P.get())
+      for (const auto &PathAndData : Block.PathData) {
+        auto &PathId = PathAndData.first;
+        auto &Data = PathAndData.second;
+        auto NewPathID =
+            Merged.internPath(cantFail(P.get().expandPath(PathId)));
+        PathDataMap::iterator PathDataIt;
+        bool Inserted;
+        std::tie(PathDataIt, Inserted) = PathData.insert({NewPathID, Data});
+        if (!Inserted) {
+          auto &ExistingData = PathDataIt->second;
+          ExistingData.CallCount += Data.CallCount;
+          ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
+        }
+      }
+
+  // In the end there's a single Block, for thread 0.
+  PathDataVector Block;
+  Block.reserve(PathData.size());
+  copy(PathData, std::back_inserter(Block));
+  cantFail(Merged.addBlock({0, std::move(Block)}));
+  return Merged;
+}
+
+Expected<Profile> loadProfile(StringRef Filename) {
+  int Fd;
+  if (auto EC = sys::fs::openFileForRead(Filename, Fd))
+    return make_error<StringError>(
+        Twine("Cannot read profile from '") + Filename + "'", EC);
+
+  uint64_t FileSize;
+  if (auto EC = sys::fs::file_size(Filename, FileSize))
+    return make_error<StringError>(
+        Twine("Cannot get filesize of '") + Filename + "'", EC);
+
+  std::error_code EC;
+  sys::fs::mapped_file_region MappedFile(
+      Fd, sys::fs::mapped_file_region::mapmode::readonly, FileSize, 0, EC);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot mmap profile '") + Filename + "'", EC);
+  StringRef Data(MappedFile.data(), MappedFile.size());
+
+  Profile P;
+  uint32_t Offset = 0;
+  DataExtractor Extractor(Data, true, 8);
+
+  // For each block we get from the file:
+  while (Offset != MappedFile.size()) {
+    auto HeaderOrError = readBlockHeader(Extractor, Offset);
+    if (!HeaderOrError)
+      return HeaderOrError.takeError();
+
+    // TODO: Maybe store this header information for each block, even just for
+    // debugging?
+    const auto &Header = HeaderOrError.get();
+
+    // Read in the path data.
+    auto PathOrError = readPath(Extractor, Offset);
+    if (!PathOrError)
+      return PathOrError.takeError();
+    const auto &Path = PathOrError.get();
+
+    // For each path we encounter, we should intern it to get a PathID.
+    auto DataOrError = readData(Extractor, Offset);
+    if (!DataOrError)
+      return DataOrError.takeError();
+    auto &Data = DataOrError.get();
+
+    if (auto E =
+            P.addBlock(Profile::Block{Profile::ThreadID{Header.Thread},
+                                      {{P.internPath(Path), std::move(Data)}}}))
+      return std::move(E);
+  }
+
+  return P;
+}
+
+namespace {
+
+struct StackEntry {
+  uint64_t Timestamp;
+  Profile::FuncID FuncId;
+};
+
+} // namespace
+
+Expected<Profile> profileFromTrace(const Trace &T) {
+  Profile P;
+
+  // The implementation of the algorithm re-creates the execution of
+  // the functions based on the trace data. To do this, we set up a number of
+  // data structures to track the execution context of every thread in the
+  // Trace.
+  DenseMap<Profile::ThreadID, std::vector<StackEntry>> ThreadStacks;
+  DenseMap<Profile::ThreadID, DenseMap<Profile::PathID, Profile::Data>>
+      ThreadPathData;
+
+  //  We then do a pass through the Trace to account data on a per-thread-basis.
+  for (const auto &E : T) {
+    auto &TSD = ThreadStacks[E.TId];
+    switch (E.Type) {
+    case RecordTypes::ENTER:
+    case RecordTypes::ENTER_ARG:
+
+      // Push entries into the function call stack.
+      TSD.push_back({E.TSC, E.FuncId});
+      break;
+
+    case RecordTypes::EXIT:
+    case RecordTypes::TAIL_EXIT:
+
+      // Exits cause some accounting to happen, based on the state of the stack.
+      // For each function we pop off the stack, we take note of the path and
+      // record the cumulative state for this path. As we're doing this, we
+      // intern the path into the Profile.
+      while (!TSD.empty()) {
+        auto Top = TSD.back();
+        auto FunctionLocalTime = AbsoluteDifference(Top.Timestamp, E.TSC);
+        SmallVector<Profile::FuncID, 16> Path;
+        transform(reverse(TSD), std::back_inserter(Path),
+                  std::mem_fn(&StackEntry::FuncId));
+        auto InternedPath = P.internPath(Path);
+        auto &TPD = ThreadPathData[E.TId][InternedPath];
+        ++TPD.CallCount;
+        TPD.CumulativeLocalTime += FunctionLocalTime;
+        TSD.pop_back();
+
+        // If we've matched the corresponding entry event for this function,
+        // then we exit the loop.
+        if (Top.FuncId == E.FuncId)
+          break;
+
+        // FIXME: Consider the intermediate times and the cumulative tree time
+        // as well.
+      }
+
+      break;
+    }
+  }
+
+  // Once we've gone through the Trace, we now create one Block per thread in
+  // the Profile.
+  for (const auto &ThreadPaths : ThreadPathData) {
+    const auto &TID = ThreadPaths.first;
+    const auto &PathsData = ThreadPaths.second;
+    if (auto E = P.addBlock({
+            TID,
+            std::vector<std::pair<Profile::PathID, Profile::Data>>(
+                PathsData.begin(), PathsData.end()),
+        }))
+      return std::move(E);
+  }
+
+  return P;
+}
+
+} // namespace xray
+} // namespace llvm

llvm/trunk/unittests/XRay/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
+  XRay
   )
 
 add_llvm_unittest(XRayTests
   GraphTest.cpp
+  ProfileTest.cpp
   )
 
 add_dependencies(XRayTests intrinsics_gen)

llvm/trunk/unittests/XRay/ProfileTest.cpp

+//===- ProfileTest.cpp - XRay Profile unit tests ----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/XRay/Profile.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <numeric>
+
+namespace llvm {
+namespace xray {
+namespace {
+
+using ::testing::AllOf;
+using ::testing::ElementsAre;
+using ::testing::Eq;
+using ::testing::Field;
+using ::testing::Not;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+TEST(ProfileTest, CreateProfile) { Profile P; }
+
+TEST(ProfileTest, InternPath) {
+  Profile P;
+  auto Path0 = P.internPath({3, 2, 1});
+  auto Path1 = P.internPath({3, 2, 1});
+  auto Path2 = P.internPath({2, 1});
+  EXPECT_THAT(Path0, Eq(Path1));
+  EXPECT_THAT(Path0, Not(Eq(Path2)));
+}
+
+TEST(ProfileTest, ExpandPath) {
+  Profile P;
+  auto PathID = P.internPath({3, 2, 1});
+  auto PathOrError = P.expandPath(PathID);
+  if (!PathOrError)
+    FAIL() << "Error: " << PathOrError.takeError();
+  EXPECT_THAT(PathOrError.get(), ElementsAre(3, 2, 1));
+}
+
+TEST(ProfileTest, AddBlocks) {
+  Profile P;
+  // Expect an error on adding empty blocks.
+  EXPECT_TRUE(errorToBool(P.addBlock({})));
+
+  // Thread blocks may not be empty.
+  EXPECT_TRUE(errorToBool(P.addBlock({1, {}})));
+
+  // Thread blocks with data must succeed.
+  EXPECT_FALSE(errorToBool(P.addBlock(
+      Profile::Block{Profile::ThreadID{1},
+                     {
+                         {P.internPath({2, 1}), Profile::Data{1, 1000}},
+                         {P.internPath({3, 2, 1}), Profile::Data{10, 100}},
+                     }})));
+}
+
+TEST(ProfileTest, CopyProfile) {
+  Profile P0, P1;
+  EXPECT_FALSE(errorToBool(P0.addBlock(
+      Profile::Block{Profile::ThreadID{1},
+                     {
+                         {P0.internPath({2, 1}), Profile::Data{1, 1000}},
+                         {P0.internPath({3, 2, 1}), Profile::Data{10, 100}},
+                     }})));
+  P1 = P0;
+  EXPECT_THAT(
+      P1, UnorderedElementsAre(AllOf(
+              Field(&Profile::Block::Thread, Eq(Profile::ThreadID{1})),
+              Field(&Profile::Block::PathData,
+                    UnorderedElementsAre(
+                        Pair(P1.internPath({2, 1}),
+                             AllOf(Field(&Profile::Data::CallCount, Eq(1u)),
+                                   Field(&Profile::Data::CumulativeLocalTime,
+                                         Eq(1000u)))),
+                        Pair(P1.internPath({3, 2, 1}),
+                             AllOf(Field(&Profile::Data::CallCount, Eq(10u)),
+                                   Field(&Profile::Data::CumulativeLocalTime,
+                                         Eq(100u)))))))));
+}
+
+TEST(ProfileTest, MoveProfile) {
+  Profile P0, P1;
+  EXPECT_FALSE(errorToBool(P0.addBlock(
+      Profile::Block{Profile::ThreadID{1},
+                     {
+                         {P0.internPath({2, 1}), Profile::Data{1, 1000}},
+                         {P0.internPath({3, 2, 1}), Profile::Data{10, 100}},
+                     }})));
+  P1 = std::move(P0);
+  EXPECT_THAT(
+      P1, UnorderedElementsAre(AllOf(
+              Field(&Profile::Block::Thread, Eq(Profile::ThreadID{1})),
+              Field(&Profile::Block::PathData,
+                    UnorderedElementsAre(
+                        Pair(P1.internPath({2, 1}),
+                             AllOf(Field(&Profile::Data::CallCount, Eq(1u)),
+                                   Field(&Profile::Data::CumulativeLocalTime,
+                                         Eq(1000u)))),
+                        Pair(P1.internPath({3, 2, 1}),
+                             AllOf(Field(&Profile::Data::CallCount, Eq(10u)),
+                                   Field(&Profile::Data::CumulativeLocalTime,
+                                         Eq(100u)))))))));
+  EXPECT_THAT(P0, UnorderedElementsAre());
+}
+
+TEST(ProfileTest, MergeProfilesByThread) {
+  Profile P0, P1;
+
+  // Set up the blocks for two different threads in P0.
+  EXPECT_FALSE(errorToBool(P0.addBlock(
+      Profile::Block{Profile::ThreadID{1},
+                     {{P0.internPath({2, 1}), Profile::Data{1, 1000}},
+                      {P0.internPath({4, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(P0.addBlock(
+      Profile::Block{Profile::ThreadID{2},
+                     {{P0.internPath({3, 1}), Profile::Data{1, 1000}}}})));
+
+  // Set up the blocks for two different threads in P1.
+  EXPECT_FALSE(errorToBool(P1.addBlock(
+      Profile::Block{Profile::ThreadID{1},
+                     {{P1.internPath({2, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(P1.addBlock(
+      Profile::Block{Profile::ThreadID{2},
+                     {{P1.internPath({3, 1}), Profile::Data{1, 1000}},
+                      {P1.internPath({4, 1}), Profile::Data{1, 1000}}}})));
+
+  Profile Merged = mergeProfilesByThread(P0, P1);
+  EXPECT_THAT(
+      Merged,
+      UnorderedElementsAre(
+          // We want to see two threads after the merge.
+          AllOf(Field(&Profile::Block::Thread, Eq(Profile::ThreadID{1})),
+                Field(&Profile::Block::PathData,
+                      UnorderedElementsAre(
+                          Pair(Merged.internPath({2, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(2u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(2000u)))),
+                          Pair(Merged.internPath({4, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(1u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(1000u))))))),
+          AllOf(Field(&Profile::Block::Thread, Eq(Profile::ThreadID{2})),
+                Field(&Profile::Block::PathData,
+                      UnorderedElementsAre(
+                          Pair(Merged.internPath({3, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(2u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(2000u)))),
+                          Pair(Merged.internPath({4, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(1u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(1000u)))))))));
+}
+
+TEST(ProfileTest, MergeProfilesByStack) {
+  Profile P0, P1;
+  EXPECT_FALSE(errorToBool(P0.addBlock(
+      Profile::Block{Profile::ThreadID{1},
+                     {{P0.internPath({2, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(P1.addBlock(
+      Profile::Block{Profile::ThreadID{2},
+                     {{P1.internPath({2, 1}), Profile::Data{1, 1000}}}})));
+
+  Profile Merged = mergeProfilesByStack(P0, P1);
+  EXPECT_THAT(Merged,
+              ElementsAre(AllOf(
+                  // We expect that we lose the ThreadID dimension in this
+                  // algorithm.
+                  Field(&Profile::Block::Thread, Eq(Profile::ThreadID{0})),
+                  Field(&Profile::Block::PathData,
+                        ElementsAre(Pair(
+                            Merged.internPath({2, 1}),
+                            AllOf(Field(&Profile::Data::CallCount, Eq(2u)),
+                                  Field(&Profile::Data::CumulativeLocalTime,
+                                        Eq(2000u)))))))));
+}
+
+TEST(ProfileTest, MergeProfilesByStackAccumulate) {
+  std::vector<Profile> Profiles(3);
+  EXPECT_FALSE(errorToBool(Profiles[0].addBlock(Profile::Block{
+      Profile::ThreadID{1},
+      {{Profiles[0].internPath({2, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(Profiles[1].addBlock(Profile::Block{
+      Profile::ThreadID{2},
+      {{Profiles[1].internPath({2, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(Profiles[2].addBlock(Profile::Block{
+      Profile::ThreadID{3},
+      {{Profiles[2].internPath({2, 1}), Profile::Data{1, 1000}}}})));
+  Profile Merged = std::accumulate(Profiles.begin(), Profiles.end(), Profile(),
+                                   mergeProfilesByStack);
+  EXPECT_THAT(Merged,
+              ElementsAre(AllOf(
+                  // We expect that we lose the ThreadID dimension in this
+                  // algorithm.
+                  Field(&Profile::Block::Thread, Eq(Profile::ThreadID{0})),
+                  Field(&Profile::Block::PathData,
+                        ElementsAre(Pair(
+                            Merged.internPath({2, 1}),
+                            AllOf(Field(&Profile::Data::CallCount, Eq(3u)),
+                                  Field(&Profile::Data::CumulativeLocalTime,
+                                        Eq(3000u)))))))));
+}
+
+TEST(ProfileTest, MergeProfilesByThreadAccumulate) {
+  std::vector<Profile> Profiles(2);
+
+  // Set up the blocks for two different threads in Profiles[0].
+  EXPECT_FALSE(errorToBool(Profiles[0].addBlock(Profile::Block{
+      Profile::ThreadID{1},
+      {{Profiles[0].internPath({2, 1}), Profile::Data{1, 1000}},
+       {Profiles[0].internPath({4, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(Profiles[0].addBlock(Profile::Block{
+      Profile::ThreadID{2},
+      {{Profiles[0].internPath({3, 1}), Profile::Data{1, 1000}}}})));
+
+  // Set up the blocks for two different threads in Profiles[1].
+  EXPECT_FALSE(errorToBool(Profiles[1].addBlock(Profile::Block{
+      Profile::ThreadID{1},
+      {{Profiles[1].internPath({2, 1}), Profile::Data{1, 1000}}}})));
+  EXPECT_FALSE(errorToBool(Profiles[1].addBlock(Profile::Block{
+      Profile::ThreadID{2},
+      {{Profiles[1].internPath({3, 1}), Profile::Data{1, 1000}},
+       {Profiles[1].internPath({4, 1}), Profile::Data{1, 1000}}}})));
+
+  Profile Merged = std::accumulate(Profiles.begin(), Profiles.end(), Profile(),
+                                   mergeProfilesByThread);
+  EXPECT_THAT(
+      Merged,
+      UnorderedElementsAre(
+          // We want to see two threads after the merge.
+          AllOf(Field(&Profile::Block::Thread, Eq(Profile::ThreadID{1})),
+                Field(&Profile::Block::PathData,
+                      UnorderedElementsAre(
+                          Pair(Merged.internPath({2, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(2u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(2000u)))),
+                          Pair(Merged.internPath({4, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(1u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(1000u))))))),
+          AllOf(Field(&Profile::Block::Thread, Eq(Profile::ThreadID{2})),
+                Field(&Profile::Block::PathData,
+                      UnorderedElementsAre(
+                          Pair(Merged.internPath({3, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(2u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(2000u)))),
+                          Pair(Merged.internPath({4, 1}),
+                               AllOf(Field(&Profile::Data::CallCount, Eq(1u)),
+                                     Field(&Profile::Data::CumulativeLocalTime,
+                                           Eq(1000u)))))))));
+}
+// FIXME: Add a test creating a Trace and generating a Profile
+// FIXME: Add tests for ranking/sorting profile blocks by dimension
+
+} // namespace
+} // namespace xray
+} // namespace llvm