cmd/compile: add control flow graphs to ssa.html

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>

1 files changed, 333 insertions, 11 deletions

diff --git a/src/cmd/compile/internal/ssa/html.go b/src/cmd/compile/internal/ssa/html.go
index d76d7c7b33..3ea83f90a2 100644
--- a/src/cmd/compile/internal/ssa/html.go
+++ b/src/cmd/compile/internal/ssa/html.go
@@ -11,6 +11,7 @@ import (
 	"html"
 	"io"
 	"os"
+	"os/exec"
 	"path/filepath"
 	"strconv"
 	"strings"
@@ -20,9 +21,10 @@ type HTMLWriter struct {
 	Logger
 	w    io.WriteCloser
 	path string
+	dot  *dotWriter
 }
 
-func NewHTMLWriter(path string, logger Logger, funcname string) *HTMLWriter {
+func NewHTMLWriter(path string, logger Logger, funcname, cfgMask string) *HTMLWriter {
 	out, err := os.OpenFile(path, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644)
 	if err != nil {
 		logger.Fatalf(src.NoXPos, "%v", err)
@@ -32,6 +34,7 @@ func NewHTMLWriter(path string, logger Logger, funcname string) *HTMLWriter {
 		logger.Fatalf(src.NoXPos, "%v", err)
 	}
 	html := HTMLWriter{w: out, Logger: logger, path: filepath.Join(pwd, path)}
+	html.dot = newDotWriter(cfgMask)
 	html.start(funcname)
 	return &html
 }
@@ -211,6 +214,25 @@ dd.ssa-prog {
     color: gray;
 }
 
+.zoom {
+	position: absolute;
+	float: left;
+	white-space: nowrap;
+	background-color: #eee;
+}
+
+.zoom a:link, .zoom a:visited  {
+    text-decoration: none;
+    color: blue;
+    font-size: 16px;
+    padding: 4px 2px;
+}
+
+svg {
+    cursor: default;
+    outline: 1px solid #eee;
+}
+
 .highlight-aquamarine     { background-color: aquamarine; }
 .highlight-coral          { background-color: coral; }
 .highlight-lightpink      { background-color: lightpink; }
@@ -236,6 +258,18 @@ dd.ssa-prog {
 .outline-maroon         { outline: maroon solid 2px; }
 .outline-black          { outline: black solid 2px; }
 
+ellipse.outline-blue           { stroke-width: 2px; stroke: blue; }
+ellipse.outline-red            { stroke-width: 2px; stroke: red; }
+ellipse.outline-blueviolet     { stroke-width: 2px; stroke: blueviolet; }
+ellipse.outline-darkolivegreen { stroke-width: 2px; stroke: darkolivegreen; }
+ellipse.outline-fuchsia        { stroke-width: 2px; stroke: fuchsia; }
+ellipse.outline-sienna         { stroke-width: 2px; stroke: sienna; }
+ellipse.outline-gold           { stroke-width: 2px; stroke: gold; }
+ellipse.outline-orangered      { stroke-width: 2px; stroke: orangered; }
+ellipse.outline-teal           { stroke-width: 2px; stroke: teal; }
+ellipse.outline-maroon         { stroke-width: 2px; stroke: maroon; }
+ellipse.outline-black          { stroke-width: 2px; stroke: black; }
+
 </style>
 
 <script type="text/javascript">
@@ -413,6 +447,38 @@ window.onload = function() {
         }
         td[i].style.display = 'table-cell';
     }
+
+    // find all svg block nodes, add their block classes
+    var nodes = document.querySelectorAll('*[id^="graph_node_"]');
+    for (var i = 0; i < nodes.length; i++) {
+    	var node = nodes[i];
+    	var name = node.id.toString();
+    	var block = name.substring(name.lastIndexOf("_")+1);
+    	node.classList.remove("node");
+    	node.classList.add(block);
+        node.addEventListener('click', ssaBlockClicked);
+        var ellipse = node.getElementsByTagName('ellipse')[0];
+        ellipse.classList.add(block);
+        ellipse.addEventListener('click', ssaBlockClicked);
+    }
+
+    // make big graphs smaller
+    var targetScale = 0.5;
+    var nodes = document.querySelectorAll('*[id^="svg_graph_"]');
+    // TODO: Implement smarter auto-zoom using the viewBox attribute
+    // and in case of big graphs set the width and height of the svg graph to
+    // maximum allowed.
+    for (var i = 0; i < nodes.length; i++) {
+    	var node = nodes[i];
+    	var name = node.id.toString();
+    	var phase = name.substring(name.lastIndexOf("_")+1);
+    	var gNode = document.getElementById("g_graph_"+phase);
+    	var scale = gNode.transform.baseVal.getItem(0).matrix.a;
+    	if (scale > targetScale) {
+    		node.width.baseVal.value *= targetScale / scale;
+    		node.height.baseVal.value *= targetScale / scale;
+    	}
+    }
 };
 
 function toggle_visibility(id) {
@@ -423,7 +489,74 @@ function toggle_visibility(id) {
         e.style.display = 'block';
     }
 }
-</script>
+
+// TODO: scale the graph with the viewBox attribute.
+function graphReduce(id) {
+    var node = document.getElementById(id);
+    if (node) {
+    		node.width.baseVal.value *= 0.9;
+    		node.height.baseVal.value *= 0.9;
+    }
+    return false;
+}
+
+function graphEnlarge(id) {
+    var node = document.getElementById(id);
+    if (node) {
+    		node.width.baseVal.value *= 1.1;
+    		node.height.baseVal.value *= 1.1;
+    }
+    return false;
+}
+
+function makeDraggable(event) {
+    var svg = event.target;
+    if (window.PointerEvent) {
+        svg.addEventListener('pointerdown', startDrag);
+        svg.addEventListener('pointermove', drag);
+        svg.addEventListener('pointerup', endDrag);
+        svg.addEventListener('pointerleave', endDrag);
+    } else {
+        svg.addEventListener('mousedown', startDrag);
+        svg.addEventListener('mousemove', drag);
+        svg.addEventListener('mouseup', endDrag);
+        svg.addEventListener('mouseleave', endDrag);
+    }
+
+    var point = svg.createSVGPoint();
+    var isPointerDown = false;
+    var pointerOrigin;
+    var viewBox = svg.viewBox.baseVal;
+
+    function getPointFromEvent (event) {
+        point.x = event.clientX;
+        point.y = event.clientY;
+
+        // We get the current transformation matrix of the SVG and we inverse it
+        var invertedSVGMatrix = svg.getScreenCTM().inverse();
+        return point.matrixTransform(invertedSVGMatrix);
+    }
+
+    function startDrag(event) {
+        isPointerDown = true;
+        pointerOrigin = getPointFromEvent(event);
+    }
+
+    function drag(event) {
+        if (!isPointerDown) {
+            return;
+        }
+        event.preventDefault();
+
+        var pointerPosition = getPointFromEvent(event);
+        viewBox.x -= (pointerPosition.x - pointerOrigin.x);
+        viewBox.y -= (pointerPosition.y - pointerOrigin.y);
+    }
+
+    function endDrag(event) {
+        isPointerDown = false;
+    }
+}</script>
 
 </head>`)
 	w.WriteString("<body>")
@@ -431,7 +564,7 @@ function toggle_visibility(id) {
 	w.WriteString(html.EscapeString(name))
 	w.WriteString("</h1>")
 	w.WriteString(`
-<a href="#" onclick="toggle_visibility('help');" id="helplink">help</a>
+<a href="#" onclick="toggle_visibility('help');return false;" id="helplink">help</a>
 <div id="help">
 
 <p>
@@ -449,6 +582,11 @@ Faded out values and blocks are dead code that has not been eliminated.
 Values printed in italics have a dependency cycle.
 </p>
 
+<p>
+<b>CFG</b>: Dashed edge is for unlikely branches. Blue color is for backward edges.
+Edge with a dot means that this edge follows the order in which blocks were laidout.
+</p>
+
 </div>
 `)
 	w.WriteString("<table>")
@@ -473,8 +611,8 @@ func (w *HTMLWriter) WriteFunc(phase, title string, f *Func) {
 	if w == nil {
 		return // avoid generating HTML just to discard it
 	}
-	w.WriteColumn(phase, title, "", f.HTML())
-	// TODO: Add visual representation of f's CFG.
+	//w.WriteColumn(phase, title, "", f.HTML())
+	w.WriteColumn(phase, title, "", f.HTML(phase, w.dot))
 }
 
 // FuncLines contains source code for a function to be displayed
@@ -704,17 +842,142 @@ func (b *Block) LongHTML() string {
 	return s
 }
 
-func (f *Func) HTML() string {
-	var buf bytes.Buffer
-	fmt.Fprint(&buf, "<code>")
-	p := htmlFuncPrinter{w: &buf}
+func (f *Func) HTML(phase string, dot *dotWriter) string {
+	buf := new(bytes.Buffer)
+	if dot != nil {
+		dot.writeFuncSVG(buf, phase, f)
+	}
+	fmt.Fprint(buf, "<code>")
+	p := htmlFuncPrinter{w: buf}
 	fprintFunc(p, f)
 
 	// fprintFunc(&buf, f) // TODO: HTML, not text, <br /> for line breaks, etc.
-	fmt.Fprint(&buf, "</code>")
+	fmt.Fprint(buf, "</code>")
 	return buf.String()
 }
 
+func (d *dotWriter) writeFuncSVG(w io.Writer, phase string, f *Func) {
+	if d.broken {
+		return
+	}
+	if _, ok := d.phases[phase]; !ok {
+		return
+	}
+	cmd := exec.Command(d.path, "-Tsvg")
+	pipe, err := cmd.StdinPipe()
+	if err != nil {
+		d.broken = true
+		fmt.Println(err)
+		return
+	}
+	buf := new(bytes.Buffer)
+	cmd.Stdout = buf
+	bufErr := new(bytes.Buffer)
+	cmd.Stderr = bufErr
+	err = cmd.Start()
+	if err != nil {
+		d.broken = true
+		fmt.Println(err)
+		return
+	}
+	fmt.Fprint(pipe, `digraph "" { margin=0; size="4,40"; ranksep=.2; `)
+	id := strings.Replace(phase, " ", "-", -1)
+	fmt.Fprintf(pipe, `id="g_graph_%s";`, id)
+	fmt.Fprintf(pipe, `node [style=filled,fillcolor=white,fontsize=16,fontname="Menlo,Times,serif",margin="0.01,0.03"];`)
+	fmt.Fprintf(pipe, `edge [fontsize=16,fontname="Menlo,Times,serif"];`)
+	for i, b := range f.Blocks {
+		if b.Kind == BlockInvalid {
+			continue
+		}
+		layout := ""
+		if f.laidout {
+			layout = fmt.Sprintf(" #%d", i)
+		}
+		fmt.Fprintf(pipe, `%v [label="%v%s\n%v",id="graph_node_%v_%v",tooltip="%v"];`, b, b, layout, b.Kind, id, b, b.LongString())
+	}
+	indexOf := make([]int, f.NumBlocks())
+	for i, b := range f.Blocks {
+		indexOf[b.ID] = i
+	}
+	layoutDrawn := make([]bool, f.NumBlocks())
+
+	ponums := make([]int32, f.NumBlocks())
+	_ = postorderWithNumbering(f, ponums)
+	isBackEdge := func(from, to ID) bool {
+		return ponums[from] <= ponums[to]
+	}
+
+	for _, b := range f.Blocks {
+		for i, s := range b.Succs {
+			style := "solid"
+			color := "black"
+			arrow := "vee"
+			if b.unlikelyIndex() == i {
+				style = "dashed"
+			}
+			if f.laidout && indexOf[s.b.ID] == indexOf[b.ID]+1 {
+				// Red color means ordered edge. It overrides other colors.
+				arrow = "dotvee"
+				layoutDrawn[s.b.ID] = true
+			} else if isBackEdge(b.ID, s.b.ID) {
+				color = "blue"
+			}
+			fmt.Fprintf(pipe, `%v -> %v [label=" %d ",style="%s",color="%s",arrowhead="%s"];`, b, s.b, i, style, color, arrow)
+		}
+	}
+	if f.laidout {
+		fmt.Fprintln(pipe, `edge[constraint=false,color=gray,style=solid,arrowhead=dot];`)
+		colors := [...]string{"#eea24f", "#f38385", "#f4d164", "#ca89fc", "gray"}
+		ci := 0
+		for i := 1; i < len(f.Blocks); i++ {
+			if layoutDrawn[f.Blocks[i].ID] {
+				continue
+			}
+			fmt.Fprintf(pipe, `%s -> %s [color="%s"];`, f.Blocks[i-1], f.Blocks[i], colors[ci])
+			ci = (ci + 1) % len(colors)
+		}
+	}
+	fmt.Fprint(pipe, "}")
+	pipe.Close()
+	err = cmd.Wait()
+	if err != nil {
+		d.broken = true
+		fmt.Printf("dot: %s\n%v\n", err, bufErr.String())
+		return
+	}
+
+	svgID := "svg_graph_" + id
+	fmt.Fprintf(w, `<div class="zoom"><button onclick="return graphReduce('%s');">-</button> <button onclick="return graphEnlarge('%s');">+</button></div>`, svgID, svgID)
+	// For now, an awful hack: edit the html as it passes through
+	// our fingers, finding '<svg ' and injecting needed attributes after it.
+	err = d.copyUntil(w, buf, `<svg `)
+	if err != nil {
+		fmt.Printf("injecting attributes: %s\n", err)
+		return
+	}
+	fmt.Fprintf(w, ` id="%s" onload="makeDraggable(evt)" `, svgID)
+	io.Copy(w, buf)
+}
+
+func (b *Block) unlikelyIndex() int {
+	switch b.Likely {
+	case BranchLikely:
+		return 1
+	case BranchUnlikely:
+		return 0
+	}
+	return -1
+}
+
+func (d *dotWriter) copyUntil(w io.Writer, buf *bytes.Buffer, sep string) error {
+	i := bytes.Index(buf.Bytes(), []byte(sep))
+	if i == -1 {
+		return fmt.Errorf("couldn't find dot sep %q", sep)
+	}
+	_, err := io.CopyN(w, buf, int64(i+len(sep)))
+	return err
+}
+
 type htmlFuncPrinter struct {
 	w io.Writer
 }
@@ -752,7 +1015,6 @@ func (p htmlFuncPrinter) endBlock(b *Block) {
 	fmt.Fprint(p.w, b.LongHTML())
 	io.WriteString(p.w, "</li>")
 	io.WriteString(p.w, "</ul>")
-	// io.WriteString(p.w, "</span>")
 }
 
 func (p htmlFuncPrinter) value(v *Value, live bool) {
@@ -780,3 +1042,63 @@ func (p htmlFuncPrinter) named(n LocalSlot, vals []*Value) {
 	}
 	fmt.Fprintf(p.w, "</li>")
 }
+
+type dotWriter struct {
+	path   string
+	broken bool
+	phases map[string]bool // keys specify phases with CFGs
+}
+
+// newDotWriter returns non-nil value when mask is valid.
+// dotWriter will generate SVGs only for the phases specifed in the mask.
+// mask can contain following patterns and combinations of them:
+// *   - all of them;
+// x-y - x through y, inclusive;
+// x,y - x and y, but not the passes between.
+func newDotWriter(mask string) *dotWriter {
+	if mask == "" {
+		return nil
+	}
+	// User can specify phase name with _ instead of spaces.
+	mask = strings.Replace(mask, "_", " ", -1)
+	ph := make(map[string]bool)
+	ranges := strings.Split(mask, ",")
+	for _, r := range ranges {
+		spl := strings.Split(r, "-")
+		if len(spl) > 2 {
+			fmt.Printf("range is not valid: %v\n", mask)
+			return nil
+		}
+		var first, last int
+		if mask == "*" {
+			first = 0
+			last = len(passes) - 1
+		} else {
+			first = passIdxByName(spl[0])
+			last = passIdxByName(spl[len(spl)-1])
+		}
+		if first < 0 || last < 0 || first > last {
+			fmt.Printf("range is not valid: %v\n", r)
+			return nil
+		}
+		for p := first; p <= last; p++ {
+			ph[passes[p].name] = true
+		}
+	}
+
+	path, err := exec.LookPath("dot")
+	if err != nil {
+		fmt.Println(err)
+		return nil
+	}
+	return &dotWriter{path: path, phases: ph}
+}
+
+func passIdxByName(name string) int {
+	for i, p := range passes {
+		if p.name == name {
+			return i
+		}
+	}
+	return -1
+}