1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
// Copyright 2014 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 cha computes the call graph of a Go program using the Class
// Hierarchy Analysis (CHA) algorithm.
//
// CHA was first described in "Optimization of Object-Oriented Programs
// Using Static Class Hierarchy Analysis", Jeffrey Dean, David Grove,
// and Craig Chambers, ECOOP'95.
//
// CHA is related to RTA (see go/callgraph/rta); the difference is that
// CHA conservatively computes the entire "implements" relation between
// interfaces and concrete types ahead of time, whereas RTA uses dynamic
// programming to construct it on the fly as it encounters new functions
// reachable from main. CHA may thus include spurious call edges for
// types that haven't been instantiated yet, or types that are never
// instantiated.
//
// Since CHA conservatively assumes that all functions are address-taken
// and all concrete types are put into interfaces, it is sound to run on
// partial programs, such as libraries without a main or test function.
package cha // import "golang.org/x/tools/go/callgraph/cha"
// TODO(zpavlinovic): update CHA for how it handles generic function bodies.
import (
"go/types"
"golang.org/x/tools/go/callgraph"
"golang.org/x/tools/go/ssa"
"golang.org/x/tools/go/ssa/ssautil"
"golang.org/x/tools/go/types/typeutil"
)
// CallGraph computes the call graph of the specified program using the
// Class Hierarchy Analysis algorithm.
func CallGraph(prog *ssa.Program) *callgraph.Graph {
cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph
allFuncs := ssautil.AllFunctions(prog)
calleesOf := lazyCallees(allFuncs)
addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) {
gnode := cg.CreateNode(g)
callgraph.AddEdge(fnode, site, gnode)
}
addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) {
// Because every call to a highly polymorphic and
// frequently used abstract method such as
// (io.Writer).Write is assumed to call every concrete
// Write method in the program, the call graph can
// contain a lot of duplication.
//
// TODO(taking): opt: consider making lazyCallees public.
// Using the same benchmarks as callgraph_test.go, removing just
// the explicit callgraph.Graph construction is 4x less memory
// and is 37% faster.
// CHA 86 ms/op 16 MB/op
// lazyCallees 63 ms/op 4 MB/op
for _, g := range callees {
addEdge(fnode, site, g)
}
}
for f := range allFuncs {
fnode := cg.CreateNode(f)
for _, b := range f.Blocks {
for _, instr := range b.Instrs {
if site, ok := instr.(ssa.CallInstruction); ok {
if g := site.Common().StaticCallee(); g != nil {
addEdge(fnode, site, g)
} else {
addEdges(fnode, site, calleesOf(site))
}
}
}
}
}
return cg
}
// lazyCallees returns a function that maps a call site (in a function in fns)
// to its callees within fns.
//
// The resulting function is not concurrency safe.
func lazyCallees(fns map[*ssa.Function]bool) func(site ssa.CallInstruction) []*ssa.Function {
// funcsBySig contains all functions, keyed by signature. It is
// the effective set of address-taken functions used to resolve
// a dynamic call of a particular signature.
var funcsBySig typeutil.Map // value is []*ssa.Function
// methodsByID contains all methods, grouped by ID for efficient
// lookup.
//
// We must key by ID, not name, for correct resolution of interface
// calls to a type with two (unexported) methods spelled the same but
// from different packages. The fact that the concrete type implements
// the interface does not mean the call dispatches to both methods.
methodsByID := make(map[string][]*ssa.Function)
// An imethod represents an interface method I.m.
// (There's no go/types object for it;
// a *types.Func may be shared by many interfaces due to interface embedding.)
type imethod struct {
I *types.Interface
id string
}
// methodsMemo records, for every abstract method call I.m on
// interface type I, the set of concrete methods C.m of all
// types C that satisfy interface I.
//
// Abstract methods may be shared by several interfaces,
// hence we must pass I explicitly, not guess from m.
//
// methodsMemo is just a cache, so it needn't be a typeutil.Map.
methodsMemo := make(map[imethod][]*ssa.Function)
lookupMethods := func(I *types.Interface, m *types.Func) []*ssa.Function {
id := m.Id()
methods, ok := methodsMemo[imethod{I, id}]
if !ok {
for _, f := range methodsByID[id] {
C := f.Signature.Recv().Type() // named or *named
if types.Implements(C, I) {
methods = append(methods, f)
}
}
methodsMemo[imethod{I, id}] = methods
}
return methods
}
for f := range fns {
if f.Signature.Recv() == nil {
// Package initializers can never be address-taken.
if f.Name() == "init" && f.Synthetic == "package initializer" {
continue
}
funcs, _ := funcsBySig.At(f.Signature).([]*ssa.Function)
funcs = append(funcs, f)
funcsBySig.Set(f.Signature, funcs)
} else if obj := f.Object(); obj != nil {
id := obj.(*types.Func).Id()
methodsByID[id] = append(methodsByID[id], f)
}
}
return func(site ssa.CallInstruction) []*ssa.Function {
call := site.Common()
if call.IsInvoke() {
tiface := call.Value.Type().Underlying().(*types.Interface)
return lookupMethods(tiface, call.Method)
} else if g := call.StaticCallee(); g != nil {
return []*ssa.Function{g}
} else if _, ok := call.Value.(*ssa.Builtin); !ok {
fns, _ := funcsBySig.At(call.Signature()).([]*ssa.Function)
return fns
}
return nil
}
}
|
