rta

Documentation

Overview

This package provides Rapid Type Analysis (RTA) for Go, a fast algorithm for call graph construction and discovery of reachable code (and hence dead code) and runtime types. The algorithm was first described in:

David F. Bacon and Peter F. Sweeney. 1996. Fast static analysis of C++ virtual function calls. (OOPSLA '96) http://doi.acm.org/10.1145/236337.236371

The algorithm uses dynamic programming to tabulate the cross-product of the set of known "address taken" functions with the set of known dynamic calls of the same type. As each new address-taken function is discovered, call graph edges are added from each known callsite, and as each new call site is discovered, call graph edges are added from it to each known address-taken function.

A similar approach is used for dynamic calls via interfaces: it tabulates the cross-product of the set of known "runtime types", i.e. types that may appear in an interface value, or be derived from one via reflection, with the set of known "invoke"-mode dynamic calls. As each new "runtime type" is discovered, call edges are added from the known call sites, and as each new call site is discovered, call graph edges are added to each compatible method.

In addition, we must consider all exported methods of any runtime type as reachable, since they may be called via reflection.

Each time a newly added call edge causes a new function to become reachable, the code of that function is analyzed for more call sites, address-taken functions, and runtime types. The process continues until a fixed point is achieved.

The resulting call graph is less precise than one produced by pointer analysis, but the algorithm is much faster. For example, running the cmd/callgraph tool on its own source takes ~2.1s for RTA and ~5.4s for points-to analysis.

Index

• type Result
  • func Analyze(roots []*ssa.Function, buildCallGraph bool) *Result

Types

type Result

type Result struct {
	// CallGraph is the discovered callgraph.
	// It does not include edges for calls made via reflection.
	CallGraph *callgraph.Graph

	// Reachable contains the set of reachable functions and methods.
	// This includes exported methods of runtime types, since
	// they may be accessed via reflection.
	// The value indicates whether the function is address-taken.
	//
	// (We wrap the bool in a struct to avoid inadvertent use of
	// "if Reachable[f] {" to test for set membership.)
	Reachable map[*ssa.Function]struct{ AddrTaken bool }

	// RuntimeTypes contains the set of types that are needed at
	// runtime, for interfaces or reflection.
	//
	// The value indicates whether the type is inaccessible to reflection.
	// Consider:
	// 	type A struct{B}
	// 	fmt.Println(new(A))
	// Types *A, A and B are accessible to reflection, but the unnamed
	// type struct{B} is not.
	RuntimeTypes typeutil.Map
}

A Result holds the results of Rapid Type Analysis, which includes the set of reachable functions/methods, runtime types, and the call graph.

func Analyze

func Analyze(roots []*ssa.Function, buildCallGraph bool) *Result

Analyze performs Rapid Type Analysis, starting at the specified root functions. It returns nil if no roots were specified.

If buildCallGraph is true, Result.CallGraph will contain a call graph; otherwise, only the other fields (reachable functions) are populated.