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 ir 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([]*Func, bool) 34 visitgen uint32 35 nodeID map[*Func]uint32 36 stack []*Func 37 } 38 39 // VisitFuncsBottomUp 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 VisitFuncsBottomUp(list []*Func, analyze func(list []*Func, recursive bool)) { 53 var v bottomUpVisitor 54 v.analyze = analyze 55 v.nodeID = make(map[*Func]uint32) 56 for _, n := range list { 57 if !n.IsHiddenClosure() { 58 v.visit(n) 59 } 60 } 61 } 62 63 func (v *bottomUpVisitor) visit(n *Func) 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 do := func(defn Node) { 77 if defn != nil { 78 if m := v.visit(defn.(*Func)); m < min { 79 min = m 80 } 81 } 82 } 83 84 Visit(n, func(n Node) { 85 switch n.Op() { 86 case ONAME: 87 if n := n.(*Name); n.Class == PFUNC { 88 do(n.Defn) 89 } 90 case ODOTMETH, OMETHVALUE, OMETHEXPR: 91 if fn := MethodExprName(n); fn != nil { 92 do(fn.Defn) 93 } 94 case OCLOSURE: 95 n := n.(*ClosureExpr) 96 do(n.Func) 97 } 98 }) 99 100 if (min == id || min == id+1) && !n.IsHiddenClosure() { 101 // This node is the root of a strongly connected component. 102 103 // The original min was id+1. If the bottomUpVisitor found its way 104 // back to id, then this block is a set of mutually recursive functions. 105 // Otherwise, it's just a lone function that does not recurse. 106 recursive := min == id 107 108 // Remove connected component from stack and mark v.nodeID so that future 109 // visits return a large number, which will not affect the caller's min. 110 var i int 111 for i = len(v.stack) - 1; i >= 0; i-- { 112 x := v.stack[i] 113 v.nodeID[x] = ^uint32(0) 114 if x == n { 115 break 116 } 117 } 118 block := v.stack[i:] 119 // Call analyze on this set of functions. 120 v.stack = v.stack[:i] 121 v.analyze(block, recursive) 122 } 123 124 return min 125 } 126