cmd/compile: add CFG graphs to ssa.html

[ysmolski]

@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

[thanm]

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]

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]

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]

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]

Some example output:

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

ssa.html.zip

[gopherbot]

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

[ysmolski]

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]

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]

SGTM. I will implement it.

[ysmolski]

Zoomable and draggable CFGs. Cursor was not captured:

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

[ysmolski]

This is the design I came up with after numerous attempts:

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]

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?

[ysmolski]

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.

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]

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

[dr2chase]

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]

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

[josharian]

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