[dev.regabi] cmd/compile: move helpers into package ir [generated]

[git-generate]
cd src/cmd/compile/internal/gc
sed -i '' 's/TestBuiltin.*/& t.Skip("mkbuiltin needs fixing")/' builtin_test.go
gofmt -w builtin_test.go
rf '
	# Inline a few little-used constructors to avoid bringing them.
	ex {
		import "cmd/compile/internal/base"
		import "cmd/compile/internal/ir"
		import "cmd/compile/internal/types"
		import "cmd/internal/src"

		var typ *types.Type
		var sym *types.Sym
		var str string
		symfield(sym, typ) -> ir.NewField(base.Pos, sym, nil, typ)
		anonfield(typ) -> ir.NewField(base.Pos, nil, nil, typ)
		namedfield(str, typ) -> ir.NewField(base.Pos, lookup(str), nil, typ)

		var cp *ir.CallPartExpr
		callpartMethod(cp) -> cp.Method
		var n ir.Node
		callpartMethod(n) -> n.(*ir.CallPartExpr).Method

		var ns []ir.Node
		liststmt(ns) -> ir.NewBlockStmt(src.NoXPos, ns)
	}
	rm symfield anonfield namedfield liststmt callpartMethod

	mv maxStackVarSize MaxStackVarSize
	mv maxImplicitStackVarSize MaxImplicitStackVarSize
	mv smallArrayBytes MaxSmallArraySize
	mv MaxStackVarSize cfg.go

	mv nodbool NewBool
	mv nodintconst NewInt
	mv nodstr NewString
	mv NewBool NewInt NewString const.go

	mv Mpprec ConstPrec
	mv bigFloatVal BigFloat
	mv doesoverflow ConstOverflow
	mv isGoConst IsConstNode
	mv smallintconst IsSmallIntConst

	mv isZero IsZero
	mv islvalue IsAssignable
	mv staticValue StaticValue
	mv samesafeexpr SameSafeExpr
	mv checkPtr ShouldCheckPtr
	mv isReflectHeaderDataField IsReflectHeaderDataField
	mv paramNnames ParamNames
	mv methodSym MethodSym
	mv methodSymSuffix MethodSymSuffix
	mv methodExprFunc MethodExprFunc
	mv methodExprName MethodExprName
	mv IsZero IsAssignable StaticValue staticValue1 reassigned \
		IsIntrinsicCall \
		SameSafeExpr ShouldCheckPtr IsReflectHeaderDataField \
		ParamNames MethodSym MethodSymSuffix \
		MethodExprName MethodExprFunc \
		expr.go

	mv Curfn CurFunc
	mv funcsymname FuncSymName
	mv newFuncNameAt NewFuncNameAt
	mv setNodeNameFunc MarkFunc
	mv CurFunc FuncSymName NewFuncNameAt MarkFunc func.go

	mv isParamStackCopy IsParamStackCopy
	mv isParamHeapCopy IsParamHeapCopy
	mv nodfp RegFP
	mv IsParamStackCopy IsParamHeapCopy RegFP name.go

	mv hasUniquePos HasUniquePos
	mv setlineno SetPos
	mv initExpr InitExpr
	mv hasNamedResults HasNamedResults
	mv outervalue OuterValue
	mv HasNamedResults HasUniquePos SetPos InitExpr OuterValue EscNever node.go

	mv visitBottomUp VisitFuncsBottomUp # scc.go

	mv cfg.go \
		NewBool NewInt NewString \ # parts of const.go
		ConstPrec BigFloat ConstOverflow IsConstNode IsSmallIntConst \
		expr.go func.go name.go node.go scc.go \
		cmd/compile/internal/ir

'

Change-Id: I13402c5a2cedbf78d993a1eae2940718f23ac166
Reviewed-on: https://go-review.googlesource.com/c/go/+/279421
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

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
+}