src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

cha.go (2701B)

      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.
      4 
      5 // Package cha computes the call graph of a Go program using the Class
      6 // Hierarchy Analysis (CHA) algorithm.
      7 //
      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.
     11 //
     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
     18 // instantiated.
     19 //
     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.
     23 package cha // import "golang.org/x/tools/go/callgraph/cha"
     24 
     25 // TODO(zpavlinovic): update CHA for how it handles generic function bodies.
     26 
     27 import (
     28 	"golang.org/x/tools/go/callgraph"
     29 	"golang.org/x/tools/go/callgraph/internal/chautil"
     30 	"golang.org/x/tools/go/ssa"
     31 	"golang.org/x/tools/go/ssa/ssautil"
     32 )
     33 
     34 // CallGraph computes the call graph of the specified program using the
     35 // Class Hierarchy Analysis algorithm.
     36 func CallGraph(prog *ssa.Program) *callgraph.Graph {
     37 	cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph
     38 
     39 	allFuncs := ssautil.AllFunctions(prog)
     40 
     41 	calleesOf := lazyCallees(allFuncs)
     42 
     43 	addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) {
     44 		gnode := cg.CreateNode(g)
     45 		callgraph.AddEdge(fnode, site, gnode)
     46 	}
     47 
     48 	addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) {
     49 		// Because every call to a highly polymorphic and
     50 		// frequently used abstract method such as
     51 		// (io.Writer).Write is assumed to call every concrete
     52 		// Write method in the program, the call graph can
     53 		// contain a lot of duplication.
     54 		for _, g := range callees {
     55 			addEdge(fnode, site, g)
     56 		}
     57 	}
     58 
     59 	for f := range allFuncs {
     60 		fnode := cg.CreateNode(f)
     61 		for _, b := range f.Blocks {
     62 			for _, instr := range b.Instrs {
     63 				if site, ok := instr.(ssa.CallInstruction); ok {
     64 					if g := site.Common().StaticCallee(); g != nil {
     65 						addEdge(fnode, site, g)
     66 					} else {
     67 						addEdges(fnode, site, calleesOf(site))
     68 					}
     69 				}
     70 			}
     71 		}
     72 	}
     73 
     74 	return cg
     75 }
     76 
     77 var lazyCallees = chautil.LazyCallees