scc.go

     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 []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  
    66  func (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
View as plain text