1 // Copyright 2014 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.
5 // Package cha computes the call graph of a Go program using the Class
6 // Hierarchy Analysis (CHA) algorithm.
8 // CHA was first described in "Optimization of Object-Oriented Programs
9 // Using Static Class Hierarchy Analysis", Jeffrey Dean, David Grove,
10 // and Craig Chambers, ECOOP'95.
12 // CHA is related to RTA (see go/callgraph/rta); the difference is that
13 // CHA conservatively computes the entire "implements" relation between
14 // interfaces and concrete types ahead of time, whereas RTA uses dynamic
15 // programming to construct it on the fly as it encounters new functions
16 // reachable from main. CHA may thus include spurious call edges for
17 // types that haven't been instantiated yet, or types that are never
20 // Since CHA conservatively assumes that all functions are address-taken
21 // and all concrete types are put into interfaces, it is sound to run on
22 // partial programs, such as libraries without a main or test function.
24 package cha // import "golang.org/x/tools/go/callgraph/cha"
29 "golang.org/x/tools/go/callgraph"
30 "golang.org/x/tools/go/ssa"
31 "golang.org/x/tools/go/ssa/ssautil"
32 "golang.org/x/tools/go/types/typeutil"
35 // CallGraph computes the call graph of the specified program using the
36 // Class Hierarchy Analysis algorithm.
38 func CallGraph(prog *ssa.Program) *callgraph.Graph {
39 cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph
41 allFuncs := ssautil.AllFunctions(prog)
43 // funcsBySig contains all functions, keyed by signature. It is
44 // the effective set of address-taken functions used to resolve
45 // a dynamic call of a particular signature.
46 var funcsBySig typeutil.Map // value is []*ssa.Function
48 // methodsByName contains all methods,
49 // grouped by name for efficient lookup.
50 // (methodsById would be better but not every SSA method has a go/types ID.)
51 methodsByName := make(map[string][]*ssa.Function)
53 // An imethod represents an interface method I.m.
54 // (There's no go/types object for it;
55 // a *types.Func may be shared by many interfaces due to interface embedding.)
60 // methodsMemo records, for every abstract method call I.m on
61 // interface type I, the set of concrete methods C.m of all
62 // types C that satisfy interface I.
64 // Abstract methods may be shared by several interfaces,
65 // hence we must pass I explicitly, not guess from m.
67 // methodsMemo is just a cache, so it needn't be a typeutil.Map.
68 methodsMemo := make(map[imethod][]*ssa.Function)
69 lookupMethods := func(I *types.Interface, m *types.Func) []*ssa.Function {
71 methods, ok := methodsMemo[imethod{I, id}]
73 for _, f := range methodsByName[m.Name()] {
74 C := f.Signature.Recv().Type() // named or *named
75 if types.Implements(C, I) {
76 methods = append(methods, f)
79 methodsMemo[imethod{I, id}] = methods
84 for f := range allFuncs {
85 if f.Signature.Recv() == nil {
86 // Package initializers can never be address-taken.
87 if f.Name() == "init" && f.Synthetic == "package initializer" {
90 funcs, _ := funcsBySig.At(f.Signature).([]*ssa.Function)
91 funcs = append(funcs, f)
92 funcsBySig.Set(f.Signature, funcs)
94 methodsByName[f.Name()] = append(methodsByName[f.Name()], f)
98 addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) {
99 gnode := cg.CreateNode(g)
100 callgraph.AddEdge(fnode, site, gnode)
103 addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) {
104 // Because every call to a highly polymorphic and
105 // frequently used abstract method such as
106 // (io.Writer).Write is assumed to call every concrete
107 // Write method in the program, the call graph can
108 // contain a lot of duplication.
110 // TODO(adonovan): opt: consider factoring the callgraph
111 // API so that the Callers component of each edge is a
112 // slice of nodes, not a singleton.
113 for _, g := range callees {
114 addEdge(fnode, site, g)
118 for f := range allFuncs {
119 fnode := cg.CreateNode(f)
120 for _, b := range f.Blocks {
121 for _, instr := range b.Instrs {
122 if site, ok := instr.(ssa.CallInstruction); ok {
123 call := site.Common()
125 tiface := call.Value.Type().Underlying().(*types.Interface)
126 addEdges(fnode, site, lookupMethods(tiface, call.Method))
127 } else if g := call.StaticCallee(); g != nil {
128 addEdge(fnode, site, g)
129 } else if _, ok := call.Value.(*ssa.Builtin); !ok {
130 callees, _ := funcsBySig.At(call.Signature()).([]*ssa.Function)
131 addEdges(fnode, site, callees)