From 829c140f149dba8933dea0cead3a78de4c83b529 Mon Sep 17 00:00:00 2001 From: Matthew Dempsky Date: Thu, 14 Mar 2019 13:54:05 -0700 Subject: [PATCH] cmd/compile: move Strongly Connected Components code into new file This logic is used by the current escape analysis pass, but otherwise logically independent. Move (unchanged) into a separate file to make that clearer, and to make it easier to replace esc.go later. Updates #23109. Change-Id: Iec8c0c47ea04c0008165791731c11d9104d5a474 Reviewed-on: https://go-review.googlesource.com/c/go/+/167715 Reviewed-by: Robert Griesemer --- src/cmd/compile/internal/gc/esc.go | 138 --------------------------- src/cmd/compile/internal/gc/scc.go | 145 +++++++++++++++++++++++++++++ 2 files changed, 145 insertions(+), 138 deletions(-) create mode 100644 src/cmd/compile/internal/gc/scc.go diff --git a/src/cmd/compile/internal/gc/esc.go b/src/cmd/compile/internal/gc/esc.go index c533439cc8..42ced85ca2 100644 --- a/src/cmd/compile/internal/gc/esc.go +++ b/src/cmd/compile/internal/gc/esc.go @@ -11,144 +11,6 @@ import ( "strings" ) -// 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([]*Node, bool) - visitgen uint32 - nodeID map[*Node]uint32 - stack []*Node -} - -// visitBottomUp 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 visitBottomUp(list []*Node, analyze func(list []*Node, recursive bool)) { - var v bottomUpVisitor - v.analyze = analyze - v.nodeID = make(map[*Node]uint32) - for _, n := range list { - if n.Op == ODCLFUNC && !n.Func.IsHiddenClosure() { - v.visit(n) - } - } -} - -func (v *bottomUpVisitor) visit(n *Node) 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) - min = v.visitcodelist(n.Nbody, min) - if (min == id || min == id+1) && !n.Func.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 -} - -func (v *bottomUpVisitor) visitcodelist(l Nodes, min uint32) uint32 { - for _, n := range l.Slice() { - min = v.visitcode(n, min) - } - return min -} - -func (v *bottomUpVisitor) visitcode(n *Node, min uint32) uint32 { - if n == nil { - return min - } - - min = v.visitcodelist(n.Ninit, min) - min = v.visitcode(n.Left, min) - min = v.visitcode(n.Right, min) - min = v.visitcodelist(n.List, min) - min = v.visitcodelist(n.Nbody, min) - min = v.visitcodelist(n.Rlist, min) - - switch n.Op { - case OCALLFUNC, OCALLMETH: - fn := asNode(n.Left.Type.Nname()) - if fn != nil && fn.Op == ONAME && fn.Class() == PFUNC && fn.Name.Defn != nil { - m := v.visit(fn.Name.Defn) - if m < min { - min = m - } - } - - case OCLOSURE: - m := v.visit(n.Func.Closure) - if m < min { - min = m - } - } - - return min -} - // Escape analysis. // An escape analysis pass for a set of functions. The diff --git a/src/cmd/compile/internal/gc/scc.go b/src/cmd/compile/internal/gc/scc.go new file mode 100644 index 0000000000..80d5be6549 --- /dev/null +++ b/src/cmd/compile/internal/gc/scc.go @@ -0,0 +1,145 @@ +// 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 gc + +// 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([]*Node, bool) + visitgen uint32 + nodeID map[*Node]uint32 + stack []*Node +} + +// visitBottomUp 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 visitBottomUp(list []*Node, analyze func(list []*Node, recursive bool)) { + var v bottomUpVisitor + v.analyze = analyze + v.nodeID = make(map[*Node]uint32) + for _, n := range list { + if n.Op == ODCLFUNC && !n.Func.IsHiddenClosure() { + v.visit(n) + } + } +} + +func (v *bottomUpVisitor) visit(n *Node) 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) + min = v.visitcodelist(n.Nbody, min) + if (min == id || min == id+1) && !n.Func.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 +} + +func (v *bottomUpVisitor) visitcodelist(l Nodes, min uint32) uint32 { + for _, n := range l.Slice() { + min = v.visitcode(n, min) + } + return min +} + +func (v *bottomUpVisitor) visitcode(n *Node, min uint32) uint32 { + if n == nil { + return min + } + + min = v.visitcodelist(n.Ninit, min) + min = v.visitcode(n.Left, min) + min = v.visitcode(n.Right, min) + min = v.visitcodelist(n.List, min) + min = v.visitcodelist(n.Nbody, min) + min = v.visitcodelist(n.Rlist, min) + + switch n.Op { + case OCALLFUNC, OCALLMETH: + fn := asNode(n.Left.Type.Nname()) + if fn != nil && fn.Op == ONAME && fn.Class() == PFUNC && fn.Name.Defn != nil { + m := v.visit(fn.Name.Defn) + if m < min { + min = m + } + } + + case OCLOSURE: + m := v.visit(n.Func.Closure) + if m < min { + min = m + } + } + + return min +} -- 2.50.0