Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: add CFG graphs to ssa.html #28177

Closed
ysmolski opened this issue Oct 12, 2018 · 17 comments
Closed

cmd/compile: add CFG graphs to ssa.html #28177

ysmolski opened this issue Oct 12, 2018 · 17 comments

Comments

@ysmolski
Copy link
Member

ysmolski commented Oct 12, 2018

@josharian has abandoned the effort in CL 43464, but I am reviving the issue here because I think there is a value and a possibility to make it happen.

Here I propose to discuss how you would specify phases with CFG created for them in ssa.html.

In my tests I used simple regexp, but I want to make it easier to use. This is how it looks right now:

% GOSSAFUNC=f:schedule-layout go build
SVG schedule
SVG layout
dumped SSA to /Users/.../ssa.html
% GOSSAFUNC=f:layout,critical go build
SVG critical
SVG layout
dumped SSA to /Users/.../ssa.html

It's not good. What about using ranges:

* -> all phases
lower -> just this one
branchelim-writebarrier -> branchelim, fuse, dse and writebarrier
a-b,d-e -> everything in between those ranges

It should reduce the time needed to generate ssa.html. Generating CFGs for two phases is almost instant.

@randall77 @josharian @dr2chase

@ysmolski ysmolski added this to the Unplanned milestone Oct 12, 2018
@thanm
Copy link
Contributor

thanm commented Oct 12, 2018

Forgive the drive-by comment, but can I suggest that the graph(s) be emitted to a separate DOT file (or files), as opposed to being emitted in rendered form in the HTML?

My experience with other compilers is that for any reasonably interesting function the graphs are too large to view on a web page, and that you really have to use some sort of tool that supports zoom-in/zoom-out, search, etc. I like to use this tool myself:

http://zvtm.sourceforge.net/zgrviewer.html

@josharian
Copy link
Contributor

FWIW, the reason I embedded it in the html is that you can then hightlight blocks and values by clicking, and have it hooked up to the rest of the page. I found that to be really useful in practice. But yes, with large graphs, it creates problems. On the other hand, large functions are generally difficult in the ssa html. And restricting cfgs to a few passes might help. (Or we could do both. I just want to make the case for why I originally chose embedding in html.)

@dr2chase
Copy link
Contributor

dr2chase commented Oct 12, 2018

I endorse the embed-in-html reasoning, though we might need to go a few rounds on this to get it right. The graph needs to look good in a narrow column if that is possible. Maybe color or dash code edges for forward/back or likely/unlikely and perhaps special case the things that are usually uninteresting (edges to exits, edge to/from write barriers).

If we want or need an option for emitting them separately into standalone .dot files, there's also some machinery in compile.go for dumping only after specified phases, to separate files. This was intended to facilitate debugging of truly gigantic inputs that can OOM the compiler accumulating the output for ssa.html . This is currently spelled -d=ssa/<phase>/dump=<fname> which I think is relatively cumbersome.

@cherrymui
Copy link
Member

I think CFG is really useful. I have drawn it by hand from SSA dump a few times.

Another possibility: let the compiler emit some simple text form of the graph (which could be just the existing SSA dump), and write a program to parse it and generate the graph, svg, dot, or whatever format. This program does not necessarily live in the Go distribution -- could be in x/tools or x/debug or somewhere else.

@ysmolski ysmolski modified the milestones: Unplanned, Unreleased Oct 15, 2018
@ysmolski ysmolski self-assigned this Oct 15, 2018
@ysmolski
Copy link
Member Author

Some example output:
screen shot 2018-10-16 at 13 06 09

And see CFGs generated with the command:
GOSSAFUNC=Benchmark_Append GOSSACFG=lower..layout go tool compile -v bench_test.go

ssa.html.zip

@gopherbot
Copy link

Change https://golang.org/cl/142517 mentions this issue: cmd/compile: add CFG graphs to ssa.html

@ysmolski
Copy link
Member Author

One problem with adding another env var GOSSACFG=lower..layout. We have to patch go cmd to be able to use it with go build. What about making it a suffix to GOSSAFUNC like so:
GOSSAFUNC=f:lower..layout ?

@dr2chase
Copy link
Contributor

I am okay with the suffix, how do you feel about f:lower-layout (lower through layout, inclusive) and f:lower,layout (lower and layout, but not the phase between) and of course a-c,x-z to mean a through c and x through z. If we want to be picky about getting the order right, that is probably acceptable, perhaps we want to warn if someone specified a phase out of order.

@ysmolski
Copy link
Member Author

SGTM. I will implement it.

@ysmolski
Copy link
Member Author

Zoomable and draggable CFGs. Cursor was not captured:
oct-18-2018 17-43-01

You can try it yourself here: https://golang.org/cl/142517.
The only TBD part is to fix colors, and text on CFGs.

@ysmolski
Copy link
Member Author

ysmolski commented Oct 30, 2018

This is the design I came up with after numerous attempts:
screen shot 2018-10-30 at 16 14 26

Blue edge is for backward edges. Dashed edge is for unlikely branches. Edge with the dot means that this edge follows the order in which blocks were laidout (ordered on layout phase).
#N in the block is the sequential number of the block in the order. What else can we display on CFG?

Please, criticise.

@dr2chase
Copy link
Contributor

As an alternative to the dot, I tried one where blue was backedge, edge-to-next was black, and out-of-order (i.e., not to next block in layout order) edge was red, and that was okay.

One problem I've had is that for more complex flow graphs, the line placement heuristics end up very "windy" and it is hard to tell exactly which is which in places. This has the color choices described above, but look at the two pale pink edges directed at b35 and b32. Can we make them less windy? Or should we choose from more than one non-black-non-blue color so that they are color-coded?

screen shot 2018-10-30 at 11 43 03 am

@ysmolski
Copy link
Member Author

ysmolski commented Oct 31, 2018

Honestly, I do not like mixing the uses of colors for two different purposes. I think that graph above, with red colors, is confusing because red color means two different things there. What I like about using dot on the edge is that it's fully orthogonal to colors. It's just another layer of information for the edge: the edge has a new characteristics (being ordered). I would like to reserver red color for some another future use and different case.

I worked on the "windy" effect of big graphs. I made a graph less compressed, but windy effect is still in place. I think that's all I could do for now. For the "ordered" edge we can use multiple colors so that close intersection do not mix. Pale colors are used only. Totally 5 different colors.
screen shot 2018-10-31 at 16 06 35

I cannot make the "dot" tool to straighten those edges. For some reason when edges do no affect the ranking of boxes, they look like a snake game.

@ysmolski
Copy link
Member Author

ysmolski commented Nov 8, 2018

@dr2chase, please examine the latest patch that generated picture in my previous post and let me know.

@dr2chase
Copy link
Contributor

dr2chase commented Nov 8, 2018

Sorry for the delay, you are not forgotten, I am just having a busy week.
You met the CL-before-freeze deadlines, and this is low risk (an option on a non-default flag), so this will certainly make 1.12. I do like the latest graph better.

Feel free to ping me a week from now if there's been no progress.

@gopherbot
Copy link

Change https://golang.org/cl/150798 mentions this issue: cmd/compile: fix TestFormats by using valid formats

gopherbot pushed a commit that referenced this issue Nov 21, 2018
CL 142517 has used some formats incorrectly. This change fixes it
by using %v for errors and invoking Block.Kind.String().
Format map stays intact.

Updates #28177

Change-Id: If53b6cc54ba3c1ffc17b005225787e3b546de404
Reviewed-on: https://go-review.googlesource.com/c/150798
Run-TryBot: Yury Smolsky <yury@smolsky.by>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
bradfitz pushed a commit that referenced this issue Nov 21, 2018
This CL adds CFGs to ssa.html.
It execs dot to generate SVG,
which then gets inlined into the html.
Some standard naming and javascript hacks
enable integration with the rest of ssa.html.
Clicking on blocks highlights the relevant
part of the CFG, and vice versa.

Sample output and screenshots can be seen in #28177.

CFGs can be turned on with the suffix mask:
:*            - dump CFG for every phase
:lower        - just the lower phase
:lower-layout - lower through layout
:w,x-y        - phases w and x through y

Calling dot after every pass is noticeably slow,
instead use the range of phases.

Dead blocks are not displayed on CFG.

User can zoom and pan individual CFG
when the automatic adjustment has failed.

Dot-related errors are reported
without bringing down the process.

Fixes #28177

Change-Id: Id52c42d86c4559ca737288aa10561b67a119c63d
Reviewed-on: https://go-review.googlesource.com/c/142517
Run-TryBot: Yury Smolsky <yury@smolsky.by>
Reviewed-by: David Chase <drchase@google.com>
bradfitz pushed a commit that referenced this issue Nov 21, 2018
CL 142517 has used some formats incorrectly. This change fixes it
by using %v for errors and invoking Block.Kind.String().
Format map stays intact.

Updates #28177

Change-Id: If53b6cc54ba3c1ffc17b005225787e3b546de404
Reviewed-on: https://go-review.googlesource.com/c/150798
Run-TryBot: Yury Smolsky <yury@smolsky.by>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
@josharian
Copy link
Contributor

Thanks again, @ysmolsky, for making this happen. Super helpful to have available when you need it.

@golang golang locked and limited conversation to collaborators May 16, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

6 participants