cmd/compile: insert scheduling checks on loop backedges

Loop breaking with a counter.  Benchmarked (see comments),
eyeball checked for sanity on popular loops.  This code
ought to handle loops in general, and properly inserts phi
functions in cases where the earlier version might not have.

Includes test, plus modifications to test/run.go to deal with
timeout and killing looping test.  Tests broken by the addition
of extra code (branch frequency and live vars) for added
checks turn the check insertion off.

If GOEXPERIMENT=preemptibleloops, the compiler inserts reschedule
checks on every backedge of every reducible loop.  Alternately,
specifying GO_GCFLAGS=-d=ssa/insert_resched_checks/on will
enable it for a single compilation, but because the core Go
libraries contain some loops that may run long, this is less
likely to have the desired effect.

This is intended as a tool to help in the study and diagnosis
of GC and other latency problems, now that goal STW GC latency
is on the order of 100 microseconds or less.

Updates #17831.
Updates #10958.

Change-Id: I6206c163a5b0248e3f21eb4fc65f73a179e1f639
Reviewed-on: https://go-review.googlesource.com/33910
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 32 insertions, 1 deletions

diff --git a/src/cmd/compile/internal/ssa/sparsetree.go b/src/cmd/compile/internal/ssa/sparsetree.go
index 7c82a60d0f..8e5b9f3e5b 100644
--- a/src/cmd/compile/internal/ssa/sparsetree.go
+++ b/src/cmd/compile/internal/ssa/sparsetree.go
@@ -4,7 +4,10 @@
 
 package ssa
 
-import "fmt"
+import (
+	"fmt"
+	"strings"
+)
 
 type SparseTreeNode struct {
 	child   *Block
@@ -67,6 +70,34 @@ func newSparseTree(f *Func, parentOf []*Block) SparseTree {
 	return t
 }
 
+// treestructure provides a string description of the dominator
+// tree and flow structure of block b and all blocks that it
+// dominates.
+func (t SparseTree) treestructure(b *Block) string {
+	return t.treestructure1(b, 0)
+}
+func (t SparseTree) treestructure1(b *Block, i int) string {
+	s := "\n" + strings.Repeat("\t", i) + b.String() + "->["
+	for i, e := range b.Succs {
+		if i > 0 {
+			s = s + ","
+		}
+		s = s + e.b.String()
+	}
+	s += "]"
+	if c0 := t[b.ID].child; c0 != nil {
+		s += "("
+		for c := c0; c != nil; c = t[c.ID].sibling {
+			if c != c0 {
+				s += " "
+			}
+			s += t.treestructure1(c, i+1)
+		}
+		s += ")"
+	}
+	return s
+}
+
 // numberBlock assigns entry and exit numbers for b and b's
 // children in an in-order walk from a gappy sequence, where n
 // is the first number not yet assigned or reserved. N should