// 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 closure function (fn.IsClosure()) 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 []*Func, analyze func(list []*Func, recursive bool)) { | |

var v bottomUpVisitor | |

v.analyze = analyze | |

v.nodeID = make(map[*Func]uint32) | |

for _, n := range list { | |

if !n.IsClosure() { | |

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) | |

do := func(defn Node) { | |

if defn != nil { | |

if m := v.visit(defn.(*Func)); m < min { | |

min = m | |

} | |

} | |

} | |

Visit(n, func(n Node) { | |

switch n.Op() { | |

case ONAME: | |

if n := n.(*Name); n.Class == PFUNC { | |

do(n.Defn) | |

} | |

case ODOTMETH, OMETHVALUE, OMETHEXPR: | |

if fn := MethodExprName(n); fn != nil { | |

do(fn.Defn) | |

} | |

case OCLOSURE: | |

n := n.(*ClosureExpr) | |

do(n.Func) | |

} | |

}) | |

if (min == id || min == id+1) && !n.IsClosure() { | |

// This node is the root of a strongly connected component. | |

// The original min was id+1. If the bottomUpVisitor found its way | |

// back to id, 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 and mark v.nodeID so that future | |

// visits return a large number, which will not affect the caller's min. | |

var i int | |

for i = len(v.stack) - 1; i >= 0; i-- { | |

x := v.stack[i] | |

v.nodeID[x] = ^uint32(0) | |

if x == n { | |

break | |

} | |

} | |

block := v.stack[i:] | |

// Call analyze on this set of functions. | |

v.stack = v.stack[:i] | |

v.analyze(block, recursive) | |

} | |

return min | |

} |