1 files changed, 289 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/escape/solve.go b/src/cmd/compile/internal/escape/solve.go
new file mode 100644
index 0000000..77d6b27
--- /dev/null
+++ b/src/cmd/compile/internal/escape/solve.go
@@ -0,0 +1,289 @@
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package escape
+
+import (
+	"cmd/compile/internal/base"
+	"cmd/compile/internal/ir"
+	"cmd/compile/internal/logopt"
+	"cmd/internal/src"
+	"fmt"
+	"strings"
+)
+
+// walkAll computes the minimal dereferences between all pairs of
+// locations.
+func (b *batch) walkAll() {
+	// We use a work queue to keep track of locations that we need
+	// to visit, and repeatedly walk until we reach a fixed point.
+	//
+	// We walk once from each location (including the heap), and
+	// then re-enqueue each location on its transition from
+	// transient->!transient and !escapes->escapes, which can each
+	// happen at most once. So we take Θ(len(e.allLocs)) walks.
+
+	// LIFO queue, has enough room for e.allLocs and e.heapLoc.
+	todo := make([]*location, 0, len(b.allLocs)+1)
+	enqueue := func(loc *location) {
+		if !loc.queued {
+			todo = append(todo, loc)
+			loc.queued = true
+		}
+	}
+
+	for _, loc := range b.allLocs {
+		enqueue(loc)
+	}
+	enqueue(&b.heapLoc)
+
+	var walkgen uint32
+	for len(todo) > 0 {
+		root := todo[len(todo)-1]
+		todo = todo[:len(todo)-1]
+		root.queued = false
+
+		walkgen++
+		b.walkOne(root, walkgen, enqueue)
+	}
+}
+
+// walkOne computes the minimal number of dereferences from root to
+// all other locations.
+func (b *batch) walkOne(root *location, walkgen uint32, enqueue func(*location)) {
+	// The data flow graph has negative edges (from addressing
+	// operations), so we use the Bellman-Ford algorithm. However,
+	// we don't have to worry about infinite negative cycles since
+	// we bound intermediate dereference counts to 0.
+
+	root.walkgen = walkgen
+	root.derefs = 0
+	root.dst = nil
+
+	todo := []*location{root} // LIFO queue
+	for len(todo) > 0 {
+		l := todo[len(todo)-1]
+		todo = todo[:len(todo)-1]
+
+		derefs := l.derefs
+
+		// If l.derefs < 0, then l's address flows to root.
+		addressOf := derefs < 0
+		if addressOf {
+			// For a flow path like "root = &l; l = x",
+			// l's address flows to root, but x's does
+			// not. We recognize this by lower bounding
+			// derefs at 0.
+			derefs = 0
+
+			// If l's address flows to a non-transient
+			// location, then l can't be transiently
+			// allocated.
+			if !root.transient && l.transient {
+				l.transient = false
+				enqueue(l)
+			}
+		}
+
+		if b.outlives(root, l) {
+			// l's value flows to root. If l is a function
+			// parameter and root is the heap or a
+			// corresponding result parameter, then record
+			// that value flow for tagging the function
+			// later.
+			if l.isName(ir.PPARAM) {
+				if (logopt.Enabled() || base.Flag.LowerM >= 2) && !l.escapes {
+					if base.Flag.LowerM >= 2 {
+						fmt.Printf("%s: parameter %v leaks to %s with derefs=%d:\n", base.FmtPos(l.n.Pos()), l.n, b.explainLoc(root), derefs)
+					}
+					explanation := b.explainPath(root, l)
+					if logopt.Enabled() {
+						var e_curfn *ir.Func // TODO(mdempsky): Fix.
+						logopt.LogOpt(l.n.Pos(), "leak", "escape", ir.FuncName(e_curfn),
+							fmt.Sprintf("parameter %v leaks to %s with derefs=%d", l.n, b.explainLoc(root), derefs), explanation)
+					}
+				}
+				l.leakTo(root, derefs)
+			}
+
+			// If l's address flows somewhere that
+			// outlives it, then l needs to be heap
+			// allocated.
+			if addressOf && !l.escapes {
+				if logopt.Enabled() || base.Flag.LowerM >= 2 {
+					if base.Flag.LowerM >= 2 {
+						fmt.Printf("%s: %v escapes to heap:\n", base.FmtPos(l.n.Pos()), l.n)
+					}
+					explanation := b.explainPath(root, l)
+					if logopt.Enabled() {
+						var e_curfn *ir.Func // TODO(mdempsky): Fix.
+						logopt.LogOpt(l.n.Pos(), "escape", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", l.n), explanation)
+					}
+				}
+				l.escapes = true
+				enqueue(l)
+				continue
+			}
+		}
+
+		for i, edge := range l.edges {
+			if edge.src.escapes {
+				continue
+			}
+			d := derefs + edge.derefs
+			if edge.src.walkgen != walkgen || edge.src.derefs > d {
+				edge.src.walkgen = walkgen
+				edge.src.derefs = d
+				edge.src.dst = l
+				edge.src.dstEdgeIdx = i
+				todo = append(todo, edge.src)
+			}
+		}
+	}
+}
+
+// explainPath prints an explanation of how src flows to the walk root.
+func (b *batch) explainPath(root, src *location) []*logopt.LoggedOpt {
+	visited := make(map[*location]bool)
+	pos := base.FmtPos(src.n.Pos())
+	var explanation []*logopt.LoggedOpt
+	for {
+		// Prevent infinite loop.
+		if visited[src] {
+			if base.Flag.LowerM >= 2 {
+				fmt.Printf("%s:   warning: truncated explanation due to assignment cycle; see golang.org/issue/35518\n", pos)
+			}
+			break
+		}
+		visited[src] = true
+		dst := src.dst
+		edge := &dst.edges[src.dstEdgeIdx]
+		if edge.src != src {
+			base.Fatalf("path inconsistency: %v != %v", edge.src, src)
+		}
+
+		explanation = b.explainFlow(pos, dst, src, edge.derefs, edge.notes, explanation)
+
+		if dst == root {
+			break
+		}
+		src = dst
+	}
+
+	return explanation
+}
+
+func (b *batch) explainFlow(pos string, dst, srcloc *location, derefs int, notes *note, explanation []*logopt.LoggedOpt) []*logopt.LoggedOpt {
+	ops := "&"
+	if derefs >= 0 {
+		ops = strings.Repeat("*", derefs)
+	}
+	print := base.Flag.LowerM >= 2
+
+	flow := fmt.Sprintf("   flow: %s = %s%v:", b.explainLoc(dst), ops, b.explainLoc(srcloc))
+	if print {
+		fmt.Printf("%s:%s\n", pos, flow)
+	}
+	if logopt.Enabled() {
+		var epos src.XPos
+		if notes != nil {
+			epos = notes.where.Pos()
+		} else if srcloc != nil && srcloc.n != nil {
+			epos = srcloc.n.Pos()
+		}
+		var e_curfn *ir.Func // TODO(mdempsky): Fix.
+		explanation = append(explanation, logopt.NewLoggedOpt(epos, "escflow", "escape", ir.FuncName(e_curfn), flow))
+	}
+
+	for note := notes; note != nil; note = note.next {
+		if print {
+			fmt.Printf("%s:     from %v (%v) at %s\n", pos, note.where, note.why, base.FmtPos(note.where.Pos()))
+		}
+		if logopt.Enabled() {
+			var e_curfn *ir.Func // TODO(mdempsky): Fix.
+			explanation = append(explanation, logopt.NewLoggedOpt(note.where.Pos(), "escflow", "escape", ir.FuncName(e_curfn),
+				fmt.Sprintf("     from %v (%v)", note.where, note.why)))
+		}
+	}
+	return explanation
+}
+
+func (b *batch) explainLoc(l *location) string {
+	if l == &b.heapLoc {
+		return "{heap}"
+	}
+	if l.n == nil {
+		// TODO(mdempsky): Omit entirely.
+		return "{temp}"
+	}
+	if l.n.Op() == ir.ONAME {
+		return fmt.Sprintf("%v", l.n)
+	}
+	return fmt.Sprintf("{storage for %v}", l.n)
+}
+
+// outlives reports whether values stored in l may survive beyond
+// other's lifetime if stack allocated.
+func (b *batch) outlives(l, other *location) bool {
+	// The heap outlives everything.
+	if l.escapes {
+		return true
+	}
+
+	// We don't know what callers do with returned values, so
+	// pessimistically we need to assume they flow to the heap and
+	// outlive everything too.
+	if l.isName(ir.PPARAMOUT) {
+		// Exception: Directly called closures can return
+		// locations allocated outside of them without forcing
+		// them to the heap. For example:
+		//
+		//    var u int  // okay to stack allocate
+		//    *(func() *int { return &u }()) = 42
+		if containsClosure(other.curfn, l.curfn) && l.curfn.ClosureCalled() {
+			return false
+		}
+
+		return true
+	}
+
+	// If l and other are within the same function, then l
+	// outlives other if it was declared outside other's loop
+	// scope. For example:
+	//
+	//    var l *int
+	//    for {
+	//        l = new(int)
+	//    }
+	if l.curfn == other.curfn && l.loopDepth < other.loopDepth {
+		return true
+	}
+
+	// If other is declared within a child closure of where l is
+	// declared, then l outlives it. For example:
+	//
+	//    var l *int
+	//    func() {
+	//        l = new(int)
+	//    }
+	if containsClosure(l.curfn, other.curfn) {
+		return true
+	}
+
+	return false
+}
+
+// containsClosure reports whether c is a closure contained within f.
+func containsClosure(f, c *ir.Func) bool {
+	// Common case.
+	if f == c {
+		return false
+	}
+
+	// Closures within function Foo are named like "Foo.funcN..."
+	// TODO(mdempsky): Better way to recognize this.
+	fn := f.Sym().Name
+	cn := c.Sym().Name
+	return len(cn) > len(fn) && cn[:len(fn)] == fn && cn[len(fn)] == '.'
+}