1 // Copyright 2011 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package gc 6 7 // Strongly connected components. 8 // 9 // Run analysis on minimal sets of mutually recursive functions 10 // or single non-recursive functions, bottom up. 11 // 12 // Finding these sets is finding strongly connected components 13 // by reverse topological order in the static call graph. 14 // The algorithm (known as Tarjan's algorithm) for doing that is taken from 15 // Sedgewick, Algorithms, Second Edition, p. 482, with two adaptations. 16 // 17 // First, a hidden closure function (n.Func.IsHiddenClosure()) cannot be the 18 // root of a connected component. Refusing to use it as a root 19 // forces it into the component of the function in which it appears. 20 // This is more convenient for escape analysis. 21 // 22 // Second, each function becomes two virtual nodes in the graph, 23 // with numbers n and n+1. We record the function's node number as n 24 // but search from node n+1. If the search tells us that the component 25 // number (min) is n+1, we know that this is a trivial component: one function 26 // plus its closures. If the search tells us that the component number is 27 // n, then there was a path from node n+1 back to node n, meaning that 28 // the function set is mutually recursive. The escape analysis can be 29 // more precise when analyzing a single non-recursive function than 30 // when analyzing a set of mutually recursive functions. 31 32 type bottomUpVisitor struct { 33 analyze func([]*Node, bool) 34 visitgen uint32 35 nodeID map[*Node]uint32 36 stack []*Node 37 } 38 39 // visitBottomUp invokes analyze on the ODCLFUNC nodes listed in list. 40 // It calls analyze with successive groups of functions, working from 41 // the bottom of the call graph upward. Each time analyze is called with 42 // a list of functions, every function on that list only calls other functions 43 // on the list or functions that have been passed in previous invocations of 44 // analyze. Closures appear in the same list as their outer functions. 45 // The lists are as short as possible while preserving those requirements. 46 // (In a typical program, many invocations of analyze will be passed just 47 // a single function.) The boolean argument 'recursive' passed to analyze 48 // specifies whether the functions on the list are mutually recursive. 49 // If recursive is false, the list consists of only a single function and its closures. 50 // If recursive is true, the list may still contain only a single function, 51 // if that function is itself recursive. 52 func visitBottomUp(list []*Node, analyze func(list []*Node, recursive bool)) { 53 var v bottomUpVisitor 54 v.analyze = analyze 55 v.nodeID = make(map[*Node]uint32) 56 for _, n := range list { 57 if n.Op == ODCLFUNC && !n.Func.IsHiddenClosure() { 58 v.visit(n) 59 } 60 } 61 } 62 63 func (v *bottomUpVisitor) visit(n *Node) uint32 { 64 if id := v.nodeID[n]; id > 0 { 65 // already visited 66 return id 67 } 68 69 v.visitgen++ 70 id := v.visitgen 71 v.nodeID[n] = id 72 v.visitgen++ 73 min := v.visitgen 74 v.stack = append(v.stack, n) 75 76 inspectList(n.Nbody, func(n *Node) bool { 77 switch n.Op { 78 case OCALLFUNC, OCALLMETH: 79 fn := asNode(n.Left.Type.Nname()) 80 if fn != nil && fn.Op == ONAME && fn.Class() == PFUNC && fn.Name.Defn != nil { 81 if m := v.visit(fn.Name.Defn); m < min { 82 min = m 83 } 84 } 85 case OCLOSURE: 86 if m := v.visit(n.Func.Closure); m < min { 87 min = m 88 } 89 } 90 return true 91 }) 92 93 if (min == id || min == id+1) && !n.Func.IsHiddenClosure() { 94 // This node is the root of a strongly connected component. 95 96 // The original min passed to visitcodelist was v.nodeID[n]+1. 97 // If visitcodelist found its way back to v.nodeID[n], then this 98 // block is a set of mutually recursive functions. 99 // Otherwise it's just a lone function that does not recurse. 100 recursive := min == id 101 102 // Remove connected component from stack. 103 // Mark walkgen so that future visits return a large number 104 // so as not to affect the caller's min. 105 106 var i int 107 for i = len(v.stack) - 1; i >= 0; i-- { 108 x := v.stack[i] 109 if x == n { 110 break 111 } 112 v.nodeID[x] = ^uint32(0) 113 } 114 v.nodeID[n] = ^uint32(0) 115 block := v.stack[i:] 116 // Run escape analysis on this set of functions. 117 v.stack = v.stack[:i] 118 v.analyze(block, recursive) 119 } 120 121 return min 122 } 123