Gecko [ 167.86.127.34 ]

Name	Size	Permission
builtin	[ DIR ]	drwxr-xr-x
testdata	[ DIR ]	drwxr-xr-x
alg.go	16.28 KB	-rw-r--r--
align.go	9.85 KB	-rw-r--r--
bexport.go	4.41 KB	-rw-r--r--
bimport.go	667 B	-rw-r--r--
bitset.go	1.15 KB	-rw-r--r--
bootstrap.go	311 B	-rw-r--r--
builtin.go	16.41 KB	-rw-r--r--
builtin_test.go	622 B	-rw-r--r--
bv.go	5.5 KB	-rw-r--r--
class_string.go	712 B	-rw-r--r--
closure.go	15.57 KB	-rw-r--r--
const.go	27.21 KB	-rw-r--r--
constFold_test.go	322.99 KB	-rw-r--r--
dcl.go	28.37 KB	-rw-r--r--
dep_test.go	587 B	-rw-r--r--
dump.go	6.37 KB	-rw-r--r--
dwinl.go	10.07 KB	-rw-r--r--
esc.go	12.22 KB	-rw-r--r--
escape.go	37.37 KB	-rw-r--r--
export.go	5.33 KB	-rw-r--r--
fixedbugs_test.go	2.23 KB	-rw-r--r--
float_test.go	11.51 KB	-rw-r--r--
fmt.go	41.71 KB	-rw-r--r--
gen.go	2.33 KB	-rw-r--r--
global_test.go	2.57 KB	-rw-r--r--
go.go	7.4 KB	-rw-r--r--
gsubr.go	9.08 KB	-rw-r--r--
iexport.go	31.65 KB	-rw-r--r--
iface_test.go	1.92 KB	-rw-r--r--
iimport.go	22.79 KB	-rw-r--r--
init.go	3.29 KB	-rw-r--r--
initorder.go	9.84 KB	-rw-r--r--
inl.go	35.08 KB	-rw-r--r--
inl_test.go	6.64 KB	-rw-r--r--
lang_test.go	1.46 KB	-rw-r--r--
lex.go	5.96 KB	-rw-r--r--
lex_test.go	3.63 KB	-rw-r--r--
logic_test.go	11.08 KB	-rw-r--r--
main.go	43.75 KB	-rw-r--r--
mapfile_mmap.go	1.21 KB	-rw-r--r--
mapfile_read.go	485 B	-rw-r--r--
mkbuiltin.go	5.34 KB	-rw-r--r--
mpfloat.go	6.56 KB	-rw-r--r--
mpint.go	5.34 KB	-rw-r--r--
noder.go	37.65 KB	-rw-r--r--
obj.go	11.44 KB	-rw-r--r--
op_string.go	4.88 KB	-rw-r--r--
order.go	37.39 KB	-rw-r--r--
pgen.go	21.66 KB	-rw-r--r--
pgen_test.go	6.01 KB	-rw-r--r--
phi.go	14.72 KB	-rw-r--r--
plive.go	44.51 KB	-rw-r--r--
pprof.go	274 B	-rw-r--r--
racewalk.go	2.61 KB	-rw-r--r--
range.go	13.72 KB	-rw-r--r--
reflect.go	48.07 KB	-rw-r--r--
reproduciblebuilds_test.go	1.46 KB	-rw-r--r--
scc.go	4.18 KB	-rw-r--r--
scope.go	2.8 KB	-rw-r--r--
scope_test.go	13.67 KB	-rw-r--r--
select.go	9.16 KB	-rw-r--r--
shift_test.go	21.46 KB	-rw-r--r--
sinit.go	26.75 KB	-rw-r--r--
sizeof_test.go	844 B	-rw-r--r--
ssa.go	224.4 KB	-rw-r--r--
ssa_test.go	5.1 KB	-rw-r--r--
subr.go	43.73 KB	-rw-r--r--
swt.go	18.51 KB	-rw-r--r--
syntax.go	36.41 KB	-rw-r--r--
timings.go	5.75 KB	-rw-r--r--
trace.go	494 B	-rw-r--r--
truncconst_test.go	1.76 KB	-rw-r--r--
typecheck.go	87.11 KB	-rw-r--r--
types.go	1.19 KB	-rw-r--r--
types_acc.go	491 B	-rw-r--r--
universe.go	10.88 KB	-rw-r--r--
unsafe.go	1.8 KB	-rw-r--r--
util.go	2.18 KB	-rw-r--r--
walk.go	101.89 KB	-rw-r--r--
zerorange_test.go	1.89 KB	-rw-r--r--

Code Editor : scc.go

// 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 gc

// 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 hidden closure function (n.Func.IsHiddenClosure()) 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([]*Node, bool)
	visitgen uint32
	nodeID   map[*Node]uint32
	stack    []*Node
}

// visitBottomUp 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 visitBottomUp(list []*Node, analyze func(list []*Node, recursive bool)) {
	var v bottomUpVisitor
	v.analyze = analyze
	v.nodeID = make(map[*Node]uint32)
	for _, n := range list {
		if n.Op == ODCLFUNC && !n.Func.IsHiddenClosure() {
			v.visit(n)
		}
	}
}

func (v *bottomUpVisitor) visit(n *Node) 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)

inspectList(n.Nbody, func(n *Node) bool {
		switch n.Op {
		case OCALLFUNC, OCALLMETH:
			fn := asNode(n.Left.Type.Nname())
			if fn != nil && fn.Op == ONAME && fn.Class() == PFUNC && fn.Name.Defn != nil {
				if m := v.visit(fn.Name.Defn); m < min {
					min = m
				}
			}
		case OCLOSURE:
			if m := v.visit(n.Func.Closure); m < min {
				min = m
			}
		}
		return true
	})

if (min == id || min == id+1) && !n.Func.IsHiddenClosure() {
		// This node is the root of a strongly connected component.

// The original min passed to visitcodelist was v.nodeID[n]+1.
		// If visitcodelist found its way back to v.nodeID[n], 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.
		// Mark walkgen so that future visits return a large number
		// so as not to affect the caller's min.

var i int
		for i = len(v.stack) - 1; i >= 0; i-- {
			x := v.stack[i]
			if x == n {
				break
			}
			v.nodeID[x] = ^uint32(0)
		}
		v.nodeID[n] = ^uint32(0)
		block := v.stack[i:]
		// Run escape analysis on this set of functions.
		v.stack = v.stack[:i]
		v.analyze(block, recursive)
	}

return min
}

${this.title}

Code Editor : scc.go