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
5package 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
32type 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.
52func VisitFuncsBottomUp(list []Node, 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.Op() == ODCLFUNC {
58			n := n.(*Func)
59			if !n.IsHiddenClosure() {
60				v.visit(n)
61			}
62		}
63	}
64}
65
66func (v *bottomUpVisitor) visit(n *Func) uint32 {
67	if id := v.nodeID[n]; id > 0 {
68		// already visited
69		return id
70	}
71
72	v.visitgen++
73	id := v.visitgen
74	v.nodeID[n] = id
75	v.visitgen++
76	min := v.visitgen
77	v.stack = append(v.stack, n)
78
79	do := func(defn Node) {
80		if defn != nil {
81			if m := v.visit(defn.(*Func)); m < min {
82				min = m
83			}
84		}
85	}
86
87	Visit(n, func(n Node) {
88		switch n.Op() {
89		case ONAME:
90			if n := n.(*Name); n.Class == PFUNC {
91				do(n.Defn)
92			}
93		case ODOTMETH, OMETHVALUE, OMETHEXPR:
94			if fn := MethodExprName(n); fn != nil {
95				do(fn.Defn)
96			}
97		case OCLOSURE:
98			n := n.(*ClosureExpr)
99			do(n.Func)
100		}
101	})
102
103	if (min == id || min == id+1) && !n.IsHiddenClosure() {
104		// This node is the root of a strongly connected component.
105
106		// The original min passed to visitcodelist was v.nodeID[n]+1.
107		// If visitcodelist found its way back to v.nodeID[n], then this
108		// block is a set of mutually recursive functions.
109		// Otherwise it's just a lone function that does not recurse.
110		recursive := min == id
111
112		// Remove connected component from stack.
113		// Mark walkgen so that future visits return a large number
114		// so as not to affect the caller's min.
115
116		var i int
117		for i = len(v.stack) - 1; i >= 0; i-- {
118			x := v.stack[i]
119			v.nodeID[x] = ^uint32(0)
120			if x == n {
121				break
122			}
123		}
124		block := v.stack[i:]
125		// Run escape analysis on this set of functions.
126		v.stack = v.stack[:i]
127		v.analyze(block, recursive)
128	}
129
130	return min
131}
132