LLVM  8.0.0svn
Profile.cpp
Go to the documentation of this file.
1 //===- Profile.cpp - XRay Profile Abstraction -----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Defines the XRay Profile class representing the latency profile generated by
11 // XRay's profiling mode.
12 //
13 //===----------------------------------------------------------------------===//
14 #include "llvm/XRay/Profile.h"
15 
17 #include "llvm/Support/Error.h"
19 #include "llvm/XRay/Trace.h"
20 #include <deque>
21 #include <memory>
22 
23 namespace llvm {
24 namespace xray {
25 
27  // We need to re-create all the tries from the original (O), into the current
28  // Profile being initialized, through the Block instances we see.
29  for (const auto &Block : O) {
30  Blocks.push_back({Block.Thread, {}});
31  auto &B = Blocks.back();
32  for (const auto &PathData : Block.PathData)
33  B.PathData.push_back({internPath(cantFail(O.expandPath(PathData.first))),
34  PathData.second});
35  }
36 }
37 
39  Profile P = O;
40  *this = std::move(P);
41  return *this;
42 }
43 
44 namespace {
45 
46 struct BlockHeader {
49  uint64_t Thread;
50 };
51 
52 static Expected<BlockHeader> readBlockHeader(DataExtractor &Extractor,
53  uint32_t &Offset) {
54  BlockHeader H;
55  uint32_t CurrentOffset = Offset;
56  H.Size = Extractor.getU32(&Offset);
57  if (Offset == CurrentOffset)
58  return make_error<StringError>(
59  Twine("Error parsing block header size at offset '") +
60  Twine(CurrentOffset) + "'",
61  std::make_error_code(std::errc::invalid_argument));
62  CurrentOffset = Offset;
63  H.Number = Extractor.getU32(&Offset);
64  if (Offset == CurrentOffset)
65  return make_error<StringError>(
66  Twine("Error parsing block header number at offset '") +
67  Twine(CurrentOffset) + "'",
68  std::make_error_code(std::errc::invalid_argument));
69  CurrentOffset = Offset;
70  H.Thread = Extractor.getU64(&Offset);
71  if (Offset == CurrentOffset)
72  return make_error<StringError>(
73  Twine("Error parsing block header thread id at offset '") +
74  Twine(CurrentOffset) + "'",
75  std::make_error_code(std::errc::invalid_argument));
76  return H;
77 }
78 
79 static Expected<std::vector<Profile::FuncID>> readPath(DataExtractor &Extractor,
80  uint32_t &Offset) {
81  // We're reading a sequence of int32_t's until we find a 0.
82  std::vector<Profile::FuncID> Path;
83  auto CurrentOffset = Offset;
84  int32_t FuncId;
85  do {
86  FuncId = Extractor.getSigned(&Offset, 4);
87  if (CurrentOffset == Offset)
88  return make_error<StringError>(
89  Twine("Error parsing path at offset '") + Twine(CurrentOffset) + "'",
90  std::make_error_code(std::errc::invalid_argument));
91  CurrentOffset = Offset;
92  Path.push_back(FuncId);
93  } while (FuncId != 0);
94  return std::move(Path);
95 }
96 
97 static Expected<Profile::Data> readData(DataExtractor &Extractor,
98  uint32_t &Offset) {
99  // We expect a certain number of elements for Data:
100  // - A 64-bit CallCount
101  // - A 64-bit CumulativeLocalTime counter
103  auto CurrentOffset = Offset;
104  D.CallCount = Extractor.getU64(&Offset);
105  if (CurrentOffset == Offset)
106  return make_error<StringError>(
107  Twine("Error parsing call counts at offset '") + Twine(CurrentOffset) +
108  "'",
109  std::make_error_code(std::errc::invalid_argument));
110  CurrentOffset = Offset;
111  D.CumulativeLocalTime = Extractor.getU64(&Offset);
112  if (CurrentOffset == Offset)
113  return make_error<StringError>(
114  Twine("Error parsing cumulative local time at offset '") +
115  Twine(CurrentOffset) + "'",
116  std::make_error_code(std::errc::invalid_argument));
117  return D;
118 }
119 
120 } // namespace
121 
123  if (B.PathData.empty())
124  return make_error<StringError>(
125  "Block may not have empty path data.",
126  std::make_error_code(std::errc::invalid_argument));
127 
128  Blocks.emplace_back(std::move(B));
129  return Error::success();
130 }
131 
133  auto It = PathIDMap.find(P);
134  if (It == PathIDMap.end())
135  return make_error<StringError>(
136  Twine("PathID not found: ") + Twine(P),
137  std::make_error_code(std::errc::invalid_argument));
138  std::vector<Profile::FuncID> Path;
139  for (auto Node = It->second; Node; Node = Node->Caller)
140  Path.push_back(Node->Func);
141  return std::move(Path);
142 }
143 
145  if (P.empty())
146  return 0;
147 
148  auto RootToLeafPath = reverse(P);
149 
150  // Find the root.
151  auto It = RootToLeafPath.begin();
152  auto PathRoot = *It++;
153  auto RootIt =
154  find_if(Roots, [PathRoot](TrieNode *N) { return N->Func == PathRoot; });
155 
156  // If we've not seen this root before, remember it.
157  TrieNode *Node = nullptr;
158  if (RootIt == Roots.end()) {
159  NodeStorage.emplace_back();
160  Node = &NodeStorage.back();
161  Node->Func = PathRoot;
162  Roots.push_back(Node);
163  } else {
164  Node = *RootIt;
165  }
166 
167  // Now traverse the path, re-creating if necessary.
168  while (It != RootToLeafPath.end()) {
169  auto NodeFuncID = *It++;
170  auto CalleeIt = find_if(Node->Callees, [NodeFuncID](TrieNode *N) {
171  return N->Func == NodeFuncID;
172  });
173  if (CalleeIt == Node->Callees.end()) {
174  NodeStorage.emplace_back();
175  auto NewNode = &NodeStorage.back();
176  NewNode->Func = NodeFuncID;
177  NewNode->Caller = Node;
178  Node->Callees.push_back(NewNode);
179  Node = NewNode;
180  } else {
181  Node = *CalleeIt;
182  }
183  }
184 
185  // At this point, Node *must* be pointing at the leaf.
186  assert(Node->Func == P.front());
187  if (Node->ID == 0) {
188  Node->ID = NextID++;
189  PathIDMap.insert({Node->ID, Node});
190  }
191  return Node->ID;
192 }
193 
195  Profile Merged;
196  using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
197  using PathDataMapPtr = std::unique_ptr<PathDataMap>;
198  using PathDataVector = decltype(Profile::Block::PathData);
199  using ThreadProfileIndexMap = DenseMap<Profile::ThreadID, PathDataMapPtr>;
200  ThreadProfileIndexMap ThreadProfileIndex;
201 
202  for (const auto &P : {std::ref(L), std::ref(R)})
203  for (const auto &Block : P.get()) {
204  ThreadProfileIndexMap::iterator It;
205  std::tie(It, std::ignore) = ThreadProfileIndex.insert(
206  {Block.Thread, PathDataMapPtr{new PathDataMap()}});
207  for (const auto &PathAndData : Block.PathData) {
208  auto &PathID = PathAndData.first;
209  auto &Data = PathAndData.second;
210  auto NewPathID =
211  Merged.internPath(cantFail(P.get().expandPath(PathID)));
212  PathDataMap::iterator PathDataIt;
213  bool Inserted;
214  std::tie(PathDataIt, Inserted) = It->second->insert({NewPathID, Data});
215  if (!Inserted) {
216  auto &ExistingData = PathDataIt->second;
217  ExistingData.CallCount += Data.CallCount;
218  ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
219  }
220  }
221  }
222 
223  for (const auto &IndexedThreadBlock : ThreadProfileIndex) {
224  PathDataVector PathAndData;
225  PathAndData.reserve(IndexedThreadBlock.second->size());
226  copy(*IndexedThreadBlock.second, std::back_inserter(PathAndData));
227  cantFail(
228  Merged.addBlock({IndexedThreadBlock.first, std::move(PathAndData)}));
229  }
230  return Merged;
231 }
232 
234  Profile Merged;
235  using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
236  PathDataMap PathData;
237  using PathDataVector = decltype(Profile::Block::PathData);
238  for (const auto &P : {std::ref(L), std::ref(R)})
239  for (const auto &Block : P.get())
240  for (const auto &PathAndData : Block.PathData) {
241  auto &PathId = PathAndData.first;
242  auto &Data = PathAndData.second;
243  auto NewPathID =
244  Merged.internPath(cantFail(P.get().expandPath(PathId)));
245  PathDataMap::iterator PathDataIt;
246  bool Inserted;
247  std::tie(PathDataIt, Inserted) = PathData.insert({NewPathID, Data});
248  if (!Inserted) {
249  auto &ExistingData = PathDataIt->second;
250  ExistingData.CallCount += Data.CallCount;
251  ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
252  }
253  }
254 
255  // In the end there's a single Block, for thread 0.
256  PathDataVector Block;
257  Block.reserve(PathData.size());
258  copy(PathData, std::back_inserter(Block));
259  cantFail(Merged.addBlock({0, std::move(Block)}));
260  return Merged;
261 }
262 
264  int Fd;
265  if (auto EC = sys::fs::openFileForRead(Filename, Fd))
266  return make_error<StringError>(
267  Twine("Cannot read profile from '") + Filename + "'", EC);
268 
269  uint64_t FileSize;
270  if (auto EC = sys::fs::file_size(Filename, FileSize))
271  return make_error<StringError>(
272  Twine("Cannot get filesize of '") + Filename + "'", EC);
273 
274  std::error_code EC;
275  sys::fs::mapped_file_region MappedFile(
276  Fd, sys::fs::mapped_file_region::mapmode::readonly, FileSize, 0, EC);
277  if (EC)
278  return make_error<StringError>(
279  Twine("Cannot mmap profile '") + Filename + "'", EC);
280  StringRef Data(MappedFile.data(), MappedFile.size());
281 
282  Profile P;
283  uint32_t Offset = 0;
284  DataExtractor Extractor(Data, true, 8);
285 
286  // For each block we get from the file:
287  while (Offset != MappedFile.size()) {
288  auto HeaderOrError = readBlockHeader(Extractor, Offset);
289  if (!HeaderOrError)
290  return HeaderOrError.takeError();
291 
292  // TODO: Maybe store this header information for each block, even just for
293  // debugging?
294  const auto &Header = HeaderOrError.get();
295 
296  // Read in the path data.
297  auto PathOrError = readPath(Extractor, Offset);
298  if (!PathOrError)
299  return PathOrError.takeError();
300  const auto &Path = PathOrError.get();
301 
302  // For each path we encounter, we should intern it to get a PathID.
303  auto DataOrError = readData(Extractor, Offset);
304  if (!DataOrError)
305  return DataOrError.takeError();
306  auto &Data = DataOrError.get();
307 
308  if (auto E =
309  P.addBlock(Profile::Block{Profile::ThreadID{Header.Thread},
310  {{P.internPath(Path), std::move(Data)}}}))
311  return std::move(E);
312  }
313 
314  return P;
315 }
316 
317 namespace {
318 
319 struct StackEntry {
320  uint64_t Timestamp;
322 };
323 
324 } // namespace
325 
327  Profile P;
328 
329  // The implementation of the algorithm re-creates the execution of
330  // the functions based on the trace data. To do this, we set up a number of
331  // data structures to track the execution context of every thread in the
332  // Trace.
335  ThreadPathData;
336 
337  // We then do a pass through the Trace to account data on a per-thread-basis.
338  for (const auto &E : T) {
339  auto &TSD = ThreadStacks[E.TId];
340  switch (E.Type) {
341  case RecordTypes::ENTER:
343 
344  // Push entries into the function call stack.
345  TSD.push_back({E.TSC, E.FuncId});
346  break;
347 
348  case RecordTypes::EXIT:
350 
351  // Exits cause some accounting to happen, based on the state of the stack.
352  // For each function we pop off the stack, we take note of the path and
353  // record the cumulative state for this path. As we're doing this, we
354  // intern the path into the Profile.
355  while (!TSD.empty()) {
356  auto Top = TSD.back();
357  auto FunctionLocalTime = AbsoluteDifference(Top.Timestamp, E.TSC);
359  transform(reverse(TSD), std::back_inserter(Path),
360  std::mem_fn(&StackEntry::FuncId));
361  auto InternedPath = P.internPath(Path);
362  auto &TPD = ThreadPathData[E.TId][InternedPath];
363  ++TPD.CallCount;
364  TPD.CumulativeLocalTime += FunctionLocalTime;
365  TSD.pop_back();
366 
367  // If we've matched the corresponding entry event for this function,
368  // then we exit the loop.
369  if (Top.FuncId == E.FuncId)
370  break;
371 
372  // FIXME: Consider the intermediate times and the cumulative tree time
373  // as well.
374  }
375 
376  break;
377  }
378  }
379 
380  // Once we've gone through the Trace, we now create one Block per thread in
381  // the Profile.
382  for (const auto &ThreadPaths : ThreadPathData) {
383  const auto &TID = ThreadPaths.first;
384  const auto &PathsData = ThreadPaths.second;
385  if (auto E = P.addBlock({
386  TID,
387  std::vector<std::pair<Profile::PathID, Profile::Data>>(
388  PathsData.begin(), PathsData.end()),
389  }))
390  return std::move(E);
391  }
392 
393  return P;
394 }
395 
396 } // namespace xray
397 } // namespace llvm
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:152
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:704
Profile::FuncID FuncId
Definition: Profile.cpp:321
uint64_t Thread
Definition: Profile.cpp:49
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
std::error_code openFileForRead(const Twine &Name, int &ResultFD, OpenFlags Flags=OF_None, SmallVectorImpl< char > *RealPath=nullptr)
Opens the file with the given name in a read-only mode, returning its open file descriptor.
int32_t FuncID
Definition: Profile.h:56
unsigned PathID
Definition: Profile.h:55
Profile mergeProfilesByStack(const Profile &L, const Profile &R)
This algorithm will merge two Profile instances into a single Profile instance, aggregating blocks by...
Definition: Profile.cpp:233
This class represents a memory mapped file.
Definition: FileSystem.h:1051
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:196
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
PathID internPath(ArrayRef< FuncID > P)
The stack represented in |P| must be in stack order (leaf to root).
Definition: Profile.cpp:144
std::error_code make_error_code(BitcodeError E)
std::error_code file_size(const Twine &Path, uint64_t &Result)
Get file size.
Definition: FileSystem.h:655
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
Expected< std::vector< FuncID > > expandPath(PathID P) const
Provides a sequence of function IDs from a previously interned PathID.
Definition: Profile.cpp:132
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
A Trace object represents the records that have been loaded from XRay log files generated by instrume...
Definition: Trace.h:47
#define P(N)
Expected< Profile > profileFromTrace(const Trace &T)
This function takes a Trace and creates a Profile instance from it.
Definition: Profile.cpp:326
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Profile & operator=(Profile &&O) noexcept
Definition: Profile.h:94
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define H(x, y, z)
Definition: MD5.cpp:57
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1070
uint32_t Number
Definition: Profile.cpp:48
static ErrorSuccess success()
Create a success value.
Definition: Error.h:327
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Profile instances are thread-compatible.
Definition: Profile.h:52
Profile mergeProfilesByThread(const Profile &L, const Profile &R)
This algorithm will merge two Profile instances into a single Profile instance, aggregating blocks by...
Definition: Profile.cpp:194
#define N
std::enable_if< std::is_unsigned< T >::value, T >::type AbsoluteDifference(T X, T Y)
Subtract two unsigned integers, X and Y, of type T and return the absolute value of the result...
Definition: MathExtras.h:767
Error addBlock(Block &&B)
Appends a fully-formed Block instance into the Profile.
Definition: Profile.cpp:122
Expected< Profile > loadProfile(StringRef Filename)
This function will attempt to load an XRay Profiling Mode profile from the provided |Filename|...
Definition: Profile.cpp:263
uint32_t Size
Definition: Profile.cpp:47
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere...
Definition: STLExtras.h:1124
uint64_t Timestamp
Definition: Profile.cpp:320
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:158
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1094
std::vector< std::pair< PathID, Data > > PathData
Definition: Profile.h:65
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144