This is an archive of the discontinued LLVM Phabricator instance.

Initial work on the XRay Graph tool.
ClosedPublic

Authored by varno on Nov 29 2016, 5:29 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

varno updated this revision to Diff 79681.Nov 29 2016, 5:29 PM
varno retitled this revision from to Initial work on the XRay Graph tool..
varno updated this object.
varno added reviewers: dberris, dblaikie.
varno added subscribers: dberris, mgorny, llvm-commits.
dblaikie added inline comments.Dec 1 2016, 1:34 PM
tools/llvm-xray/xray-graph.cc
84–88 ↗(On Diff #79681)

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.

89–91 ↗(On Diff #79681)

Consider dropping {} on single line blocks.

116–120 ↗(On Diff #79681)

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)

120 ↗(On Diff #79681)

Extra semicolon

128 ↗(On Diff #79681)

Extra semi

132–133 ↗(On Diff #79681)

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

174–183 ↗(On Diff #79681)

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
30 ↗(On Diff #79681)

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

41 ↗(On Diff #79681)

(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)

59 ↗(On Diff #79681)

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

68 ↗(On Diff #79681)

Extra semicolon

varno updated this revision to Diff 80004.Dec 1 2016, 5:46 PM
  • Initial work on the XRay Graph tool.
  • Responses to Phabricator comments
varno updated this revision to Diff 80007.Dec 1 2016, 5:49 PM

Remove spurious files by basing patch on D24377

dberris added inline comments.Dec 1 2016, 5:56 PM
tools/llvm-xray/CMakeLists.txt
16 ↗(On Diff #80007)

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

tools/llvm-xray/xray-graph.cc
174–183 ↗(On Diff #79681)

+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
41 ↗(On Diff #79681)

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 marked 8 inline comments as done.Dec 1 2016, 5:57 PM
varno added inline comments.
tools/llvm-xray/xray-graph.cc
174–183 ↗(On Diff #79681)

Yeah there probably should be. Not yet though AFAIK.

tools/llvm-xray/xray-graph.h
41 ↗(On Diff #79681)

Thinking more on this before I make changes.

59 ↗(On Diff #79681)

Thinking on this more before I make changes.

varno planned changes to this revision.Dec 1 2016, 6:52 PM

I am planning changes

varno updated this revision to Diff 80221.Dec 4 2016, 4:35 PM
  • Additional Changes in response to dblaikie's comments
  • Rebase to current version of D24377 and use getSupportedLoader
varno marked 6 inline comments as done.Dec 4 2016, 4:36 PM

I have addressed the last open comments.

dberris edited edge metadata.Dec 5 2016, 7:45 PM

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 requested changes to this revision.Dec 5 2016, 7:46 PM
dberris edited edge metadata.

Needs tests.

This revision now requires changes to proceed.Dec 5 2016, 7:46 PM
varno updated this revision to Diff 80535.Dec 6 2016, 7:41 PM
varno edited edge metadata.
  • Extra work making the xray-graph tool more powerful.
  • Further work on options in llvm-xray graph subcommand
  • Created Tests

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
121 ↗(On Diff #80535)

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

155–156 ↗(On Diff #80535)

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

tools/llvm-xray/xray-graph.h
27–28 ↗(On Diff #80535)

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

75 ↗(On Diff #80535)

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

115–124 ↗(On Diff #80535)

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?

126–127 ↗(On Diff #80535)

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

varno added inline comments.Dec 6 2016, 8:37 PM
tools/llvm-xray/xray-graph.cc
121 ↗(On Diff #80535)

No.

tools/llvm-xray/xray-graph.h
115–124 ↗(On Diff #80535)

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).

126–127 ↗(On Diff #80535)

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

varno updated this revision to Diff 80538.Dec 6 2016, 8:38 PM
varno edited edge metadata.
  • Reply to dberris comments.

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
174–175 ↗(On Diff #80538)

Empty line between these two lines?

187–196 ↗(On Diff #80538)

The indentation here is a little weird. Fix?

tools/llvm-xray/xray-graph.h
115–124 ↗(On Diff #80535)

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

126–127 ↗(On Diff #80535)

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 updated this revision to Diff 80539.Dec 6 2016, 9:08 PM
varno marked 3 inline comments as done.
  • Comments by Dberris
varno marked 5 inline comments as done.Dec 6 2016, 9:10 PM
varno added inline comments.
tools/llvm-xray/xray-graph.h
115–124 ↗(On Diff #80535)

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

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

tools/llvm-xray/xray-graph.cc
229–230 ↗(On Diff #80539)

Missing empty line between these two.

344–347 ↗(On Diff #80539)

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
115–124 ↗(On Diff #80535)

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 updated this revision to Diff 80541.Dec 6 2016, 9:51 PM
  • Replying to comments
varno marked 2 inline comments as done.Dec 6 2016, 9:54 PM
varno added inline comments.
tools/llvm-xray/xray-graph.h
115–124 ↗(On Diff #80535)

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

dberris added inline comments.Dec 6 2016, 9:59 PM
tools/llvm-xray/xray-graph.h
43–44 ↗(On Diff #80541)

Missing empty line between these two.

74–75 ↗(On Diff #80541)

Missing line in between these two.

varno updated this revision to Diff 80542.Dec 6 2016, 10:03 PM
  • Patch comment reply

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

tools/llvm-xray/xray-graph.cc
102 ↗(On Diff #80541)

Potentially spurious empty line here.

117 ↗(On Diff #80541)

Also potentially spurious empty line here.

142–148 ↗(On Diff #80541)

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

150 ↗(On Diff #80541)

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.

204–205 ↗(On Diff #80541)

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

214 ↗(On Diff #80541)

No need for void in the function arguments.

215 ↗(On Diff #80541)

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

221 ↗(On Diff #80541)

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

221–228 ↗(On Diff #80541)

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
88 ↗(On Diff #80541)

Why are the iterators not the same type?

92 ↗(On Diff #80541)

No need for void in the function arguments.

varno updated this revision to Diff 80666.Dec 7 2016, 2:34 PM
varno marked 8 inline comments as done.
  • Comments
varno marked 5 inline comments as done.Dec 7 2016, 2:50 PM
varno added inline comments.
tools/llvm-xray/xray-graph.cc
221–228 ↗(On Diff #80541)

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 updated this revision to Diff 80696.Dec 7 2016, 5:37 PM
varno marked 2 inline comments as done.
  • Reply to dberris comments.
  • Comments
  • comments
dberris accepted this revision.Dec 7 2016, 6:47 PM
dberris edited edge metadata.

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
221–228 ↗(On Diff #80541)

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.

This revision is now accepted and ready to land.Dec 7 2016, 6:47 PM
dblaikie accepted this revision.Jan 9 2017, 1:14 PM
dblaikie edited edge metadata.
dblaikie added inline comments.
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
211–212 ↗(On Diff #80696)

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

222 ↗(On Diff #80696)

Remove dead code

287–288 ↗(On Diff #80696)

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.

340–341 ↗(On Diff #80696)

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)

358 ↗(On Diff #80696)

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

varno marked 4 inline comments as done.Jan 9 2017, 2:43 PM
varno added inline comments.
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
211–212 ↗(On Diff #80696)

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 added inline comments.Jan 12 2017, 12:59 AM
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
15 ↗(On Diff #80696)

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
211–212 ↗(On Diff #80696)

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.

340–341 ↗(On Diff #80696)

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.

358 ↗(On Diff #80696)

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 updated this revision to Diff 84186.Jan 12 2017, 3:29 PM
varno edited edge metadata.

Rebase and addess comment.

varno marked 15 inline comments as done.Jan 12 2017, 3:32 PM
varno added inline comments.
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 added inline comments.Jan 12 2017, 7:01 PM
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 updated this revision to Diff 84215.Jan 12 2017, 7:43 PM
varno marked an inline comment as done.
  • Initial work on the XRay Graph tool.
  • clang-format
varno updated this revision to Diff 84216.Jan 12 2017, 7:50 PM
  • fix tests
varno added a comment.Jan 15 2017, 2:15 PM

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

This revision was automatically updated to reflect the committed changes.
labath added a subscriber: labath.Jan 17 2017, 1:52 AM

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).