1 files changed, 153 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ir/scc.go b/src/cmd/compile/internal/ir/scc.go
new file mode 100644
index 0000000000..4f646e22b5
--- /dev/null
+++ b/src/cmd/compile/internal/ir/scc.go
@@ -0,0 +1,153 @@
+// Copyright 2011 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 ir
+
+// Strongly connected components.
+//
+// Run analysis on minimal sets of mutually recursive functions
+// or single non-recursive functions, bottom up.
+//
+// Finding these sets is finding strongly connected components
+// by reverse topological order in the static call graph.
+// The algorithm (known as Tarjan's algorithm) for doing that is taken from
+// Sedgewick, Algorithms, Second Edition, p. 482, with two adaptations.
+//
+// First, a hidden closure function (n.Func.IsHiddenClosure()) cannot be the
+// root of a connected component. Refusing to use it as a root
+// forces it into the component of the function in which it appears.
+// This is more convenient for escape analysis.
+//
+// Second, each function becomes two virtual nodes in the graph,
+// with numbers n and n+1. We record the function's node number as n
+// but search from node n+1. If the search tells us that the component
+// number (min) is n+1, we know that this is a trivial component: one function
+// plus its closures. If the search tells us that the component number is
+// n, then there was a path from node n+1 back to node n, meaning that
+// the function set is mutually recursive. The escape analysis can be
+// more precise when analyzing a single non-recursive function than
+// when analyzing a set of mutually recursive functions.
+
+type bottomUpVisitor struct {
+	analyze  func([]*Func, bool)
+	visitgen uint32
+	nodeID   map[*Func]uint32
+	stack    []*Func
+}
+
+// VisitFuncsBottomUp invokes analyze on the ODCLFUNC nodes listed in list.
+// It calls analyze with successive groups of functions, working from
+// the bottom of the call graph upward. Each time analyze is called with
+// a list of functions, every function on that list only calls other functions
+// on the list or functions that have been passed in previous invocations of
+// analyze. Closures appear in the same list as their outer functions.
+// The lists are as short as possible while preserving those requirements.
+// (In a typical program, many invocations of analyze will be passed just
+// a single function.) The boolean argument 'recursive' passed to analyze
+// specifies whether the functions on the list are mutually recursive.
+// If recursive is false, the list consists of only a single function and its closures.
+// If recursive is true, the list may still contain only a single function,
+// if that function is itself recursive.
+func VisitFuncsBottomUp(list []Node, analyze func(list []*Func, recursive bool)) {
+	var v bottomUpVisitor
+	v.analyze = analyze
+	v.nodeID = make(map[*Func]uint32)
+	for _, n := range list {
+		if n.Op() == ODCLFUNC {
+			n := n.(*Func)
+			if !n.IsHiddenClosure() {
+				v.visit(n)
+			}
+		}
+	}
+}
+
+func (v *bottomUpVisitor) visit(n *Func) uint32 {
+	if id := v.nodeID[n]; id > 0 {
+		// already visited
+		return id
+	}
+
+	v.visitgen++
+	id := v.visitgen
+	v.nodeID[n] = id
+	v.visitgen++
+	min := v.visitgen
+	v.stack = append(v.stack, n)
+
+	Visit(n, func(n Node) {
+		switch n.Op() {
+		case ONAME:
+			n := n.(*Name)
+			if n.Class_ == PFUNC {
+				if n != nil && n.Name().Defn != nil {
+					if m := v.visit(n.Name().Defn.(*Func)); m < min {
+						min = m
+					}
+				}
+			}
+		case OMETHEXPR:
+			n := n.(*MethodExpr)
+			fn := MethodExprName(n)
+			if fn != nil && fn.Defn != nil {
+				if m := v.visit(fn.Defn.(*Func)); m < min {
+					min = m
+				}
+			}
+		case ODOTMETH:
+			n := n.(*SelectorExpr)
+			fn := MethodExprName(n)
+			if fn != nil && fn.Op() == ONAME && fn.Class_ == PFUNC && fn.Defn != nil {
+				if m := v.visit(fn.Defn.(*Func)); m < min {
+					min = m
+				}
+			}
+		case OCALLPART:
+			n := n.(*CallPartExpr)
+			fn := AsNode(n.Method.Nname)
+			if fn != nil && fn.Op() == ONAME {
+				if fn := fn.(*Name); fn.Class_ == PFUNC && fn.Name().Defn != nil {
+					if m := v.visit(fn.Name().Defn.(*Func)); m < min {
+						min = m
+					}
+				}
+			}
+		case OCLOSURE:
+			n := n.(*ClosureExpr)
+			if m := v.visit(n.Func); m < min {
+				min = m
+			}
+		}
+	})
+
+	if (min == id || min == id+1) && !n.IsHiddenClosure() {
+		// This node is the root of a strongly connected component.
+
+		// The original min passed to visitcodelist was v.nodeID[n]+1.
+		// If visitcodelist found its way back to v.nodeID[n], then this
+		// block is a set of mutually recursive functions.
+		// Otherwise it's just a lone function that does not recurse.
+		recursive := min == id
+
+		// Remove connected component from stack.
+		// Mark walkgen so that future visits return a large number
+		// so as not to affect the caller's min.
+
+		var i int
+		for i = len(v.stack) - 1; i >= 0; i-- {
+			x := v.stack[i]
+			if x == n {
+				break
+			}
+			v.nodeID[x] = ^uint32(0)
+		}
+		v.nodeID[n] = ^uint32(0)
+		block := v.stack[i:]
+		// Run escape analysis on this set of functions.
+		v.stack = v.stack[:i]
+		v.analyze(block, recursive)
+	}
+
+	return min
+}