go/callgraph/callgraph_test.go - tools - Git at Google

 // Copyright 2023 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 callgraph_test

 import (
 	"log"
 	"sync"
 	"testing"

 	"golang.org/x/tools/go/callgraph"
 	"golang.org/x/tools/go/callgraph/cha"
 	"golang.org/x/tools/go/callgraph/rta"
 	"golang.org/x/tools/go/callgraph/static"
 	"golang.org/x/tools/go/callgraph/vta"
 	"golang.org/x/tools/go/loader"
 	"golang.org/x/tools/go/pointer"
 	"golang.org/x/tools/go/ssa"
 	"golang.org/x/tools/go/ssa/ssautil"
 )

 // Benchmarks comparing different callgraph algorithms implemented in
 // x/tools/go/callgraph. Comparison is on both speed, memory and precision.
 // Fewer edges and fewer reachable nodes implies a more precise result.
 // Comparison is done on a hello world http server using net/http.
 //
 // Current results were on an i7 macbook on go version devel go1.20-2730.
 // Number of nodes, edges, and reachable function are expected to vary between
 // go versions. Timing results are expected to vary between machines.
 // BenchmarkStatic-12	 53 ms/op     6 MB/op	12113 nodes	 37355 edges	1522 reachable
 // BenchmarkCHA-12    	 86 ms/op	 16 MB/op	12113 nodes	131717 edges	7640 reachable
 // BenchmarkRTA-12		110 ms/op	 12 MB/op	 6566 nodes	 42291 edges	5099 reachable
 // BenchmarkPTA-12	   1427 ms/op	600 MB/op	 8714 nodes	 28244 edges	4184 reachable
 // BenchmarkVTA-12		600 ms/op	 78 MB/op	12114 nodes	 44861 edges	4919 reachable
 // BenchmarkVTA2-12		793 ms/op	104 MB/op	 5450 nodes	 22208 edges	4042 reachable
 // BenchmarkVTA3-12		977 ms/op	124 MB/op	 4621 nodes	 19331 edges	3700 reachable
 // BenchmarkVTAAlt-12	372 ms/op	 57 MB/op	 7763 nodes	 29912 edges	4258 reachable
 // BenchmarkVTAAlt2-12	570 ms/op	 78 MB/op	 4838 nodes	 20169 edges	3737 reachable
 //
 // Note:
 // * Static is unsound and may miss real edges.
 // * RTA starts from a main function and only includes reachable functions.
 // * CHA starts from all functions.
 // * VTA, VTA2, and VTA3 are starting from all functions and the CHA callgraph.
 //   VTA2 and VTA3 are the result of re-applying VTA to the functions reachable
 //   from main() via the callgraph of the previous stage.
 // * VTAAlt, and VTAAlt2 start from the functions reachable from main via the
 //   CHA callgraph.
 // * All algorithms are unsound w.r.t. reflection.

 const httpEx = `package main

 import (
     "fmt"
     "net/http"
 )

 func hello(w http.ResponseWriter, req *http.Request) {
     fmt.Fprintf(w, "hello world\n")
 }

 func main() {
     http.HandleFunc("/hello", hello)
     http.ListenAndServe(":8090", nil)
 }
 `

 var (
 	once sync.Once
 	prog *ssa.Program
 	main *ssa.Function
 )

 func example() (*ssa.Program, *ssa.Function) {
 	once.Do(func() {
 		var conf loader.Config
 		f, err := conf.ParseFile("<input>", httpEx)
 		if err != nil {
 			log.Fatal(err)
 		}
 		conf.CreateFromFiles(f.Name.Name, f)

 		lprog, err := conf.Load()
 		if err != nil {
 			log.Fatalf("test 'package %s': Load: %s", f.Name.Name, err)
 		}
 		prog = ssautil.CreateProgram(lprog, ssa.InstantiateGenerics)
 		prog.Build()

 		main = prog.Package(lprog.Created[0].Pkg).Members["main"].(*ssa.Function)
 	})
 	return prog, main
 }

 var stats bool = false // print stats?

 func logStats(b *testing.B, cnd bool, name string, cg *callgraph.Graph, main *ssa.Function) {
 	if cnd && stats {
 		e := 0
 		for _, n := range cg.Nodes {
 			e += len(n.Out)
 		}
 		r := len(reaches(main, cg, false))
 		b.Logf("%s:\t%d nodes\t%d edges\t%d reachable", name, len(cg.Nodes), e, r)
 	}
 }

 func BenchmarkStatic(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		cg := static.CallGraph(prog)
 		logStats(b, i == 0, "static", cg, main)
 	}
 }

 func BenchmarkCHA(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		cg := cha.CallGraph(prog)
 		logStats(b, i == 0, "cha", cg, main)
 	}
 }

 func BenchmarkRTA(b *testing.B) {
 	b.StopTimer()
 	_, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		res := rta.Analyze([]*ssa.Function{main}, true)
 		cg := res.CallGraph
 		logStats(b, i == 0, "rta", cg, main)
 	}
 }

 func BenchmarkPTA(b *testing.B) {
 	b.StopTimer()
 	_, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		config := &pointer.Config{Mains: []*ssa.Package{main.Pkg}, BuildCallGraph: true}
 		res, err := pointer.Analyze(config)
 		if err != nil {
 			b.Fatal(err)
 		}
 		logStats(b, i == 0, "pta", res.CallGraph, main)
 	}
 }

 func BenchmarkVTA(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		cg := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
 		logStats(b, i == 0, "vta", cg, main)
 	}
 }

 func BenchmarkVTA2(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		vta1 := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
 		cg := vta.CallGraph(reaches(main, vta1, true), vta1)
 		logStats(b, i == 0, "vta2", cg, main)
 	}
 }

 func BenchmarkVTA3(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		vta1 := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
 		vta2 := vta.CallGraph(reaches(main, vta1, true), vta1)
 		cg := vta.CallGraph(reaches(main, vta2, true), vta2)
 		logStats(b, i == 0, "vta3", cg, main)
 	}
 }

 func BenchmarkVTAAlt(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		cha := cha.CallGraph(prog)
 		cg := vta.CallGraph(reaches(main, cha, true), cha) // start from only functions reachable by CHA.
 		logStats(b, i == 0, "vta-alt", cg, main)
 	}
 }

 func BenchmarkVTAAlt2(b *testing.B) {
 	b.StopTimer()
 	prog, main := example()
 	b.StartTimer()

 	for i := 0; i < b.N; i++ {
 		cha := cha.CallGraph(prog)
 		vta1 := vta.CallGraph(reaches(main, cha, true), cha)
 		cg := vta.CallGraph(reaches(main, vta1, true), vta1)
 		logStats(b, i == 0, "vta-alt2", cg, main)
 	}
 }

 // reaches computes the transitive closure of functions forward reachable
 // via calls in cg starting from `sources`. If refs is true, include
 // functions referred to in an instruction.
 func reaches(source *ssa.Function, cg *callgraph.Graph, refs bool) map[*ssa.Function]bool {
 	seen := make(map[*ssa.Function]bool)
 	var visit func(f *ssa.Function)
 	visit = func(f *ssa.Function) {
 		if seen[f] {
 			return
 		}
 		seen[f] = true

 		if n := cg.Nodes[f]; n != nil {
 			for _, e := range n.Out {
 				if e.Site != nil {
 					visit(e.Callee.Func)
 				}
 			}
 		}

 		if refs {
 			var buf [10]*ssa.Value // avoid alloc in common case
 			for _, b := range f.Blocks {
 				for _, instr := range b.Instrs {
 					for _, op := range instr.Operands(buf[:0]) {
 						if fn, ok := (*op).(*ssa.Function); ok {
 							visit(fn)
 						}
 					}
 				}
 			}
 		}
 	}
 	visit(source)
 	return seen
 }
	// Copyright 2023 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 callgraph_test

	import (
	"log"
	"sync"
	"testing"

	"golang.org/x/tools/go/callgraph"
	"golang.org/x/tools/go/callgraph/cha"
	"golang.org/x/tools/go/callgraph/rta"
	"golang.org/x/tools/go/callgraph/static"
	"golang.org/x/tools/go/callgraph/vta"
	"golang.org/x/tools/go/loader"
	"golang.org/x/tools/go/pointer"
	"golang.org/x/tools/go/ssa"
	"golang.org/x/tools/go/ssa/ssautil"
	)

	// Benchmarks comparing different callgraph algorithms implemented in
	// x/tools/go/callgraph. Comparison is on both speed, memory and precision.
	// Fewer edges and fewer reachable nodes implies a more precise result.
	// Comparison is done on a hello world http server using net/http.
	//
	// Current results were on an i7 macbook on go version devel go1.20-2730.
	// Number of nodes, edges, and reachable function are expected to vary between
	// go versions. Timing results are expected to vary between machines.
	// BenchmarkStatic-12 53 ms/op 6 MB/op 12113 nodes 37355 edges 1522 reachable
	// BenchmarkCHA-12 86 ms/op 16 MB/op 12113 nodes 131717 edges 7640 reachable
	// BenchmarkRTA-12 110 ms/op 12 MB/op 6566 nodes 42291 edges 5099 reachable
	// BenchmarkPTA-12 1427 ms/op 600 MB/op 8714 nodes 28244 edges 4184 reachable
	// BenchmarkVTA-12 600 ms/op 78 MB/op 12114 nodes 44861 edges 4919 reachable
	// BenchmarkVTA2-12 793 ms/op 104 MB/op 5450 nodes 22208 edges 4042 reachable
	// BenchmarkVTA3-12 977 ms/op 124 MB/op 4621 nodes 19331 edges 3700 reachable
	// BenchmarkVTAAlt-12 372 ms/op 57 MB/op 7763 nodes 29912 edges 4258 reachable
	// BenchmarkVTAAlt2-12 570 ms/op 78 MB/op 4838 nodes 20169 edges 3737 reachable
	//
	// Note:
	// * Static is unsound and may miss real edges.
	// * RTA starts from a main function and only includes reachable functions.
	// * CHA starts from all functions.
	// * VTA, VTA2, and VTA3 are starting from all functions and the CHA callgraph.
	// VTA2 and VTA3 are the result of re-applying VTA to the functions reachable
	// from main() via the callgraph of the previous stage.
	// * VTAAlt, and VTAAlt2 start from the functions reachable from main via the
	// CHA callgraph.
	// * All algorithms are unsound w.r.t. reflection.

	const httpEx = `package main

	import (
	"fmt"
	"net/http"
	)

	func hello(w http.ResponseWriter, req *http.Request) {
	fmt.Fprintf(w, "hello world\n")
	}

	func main() {
	http.HandleFunc("/hello", hello)
	http.ListenAndServe(":8090", nil)
	}
	`

	var (
	once sync.Once
	prog *ssa.Program
	main *ssa.Function
	)

	func example() (ssa.Program, ssa.Function) {
	once.Do(func() {
	var conf loader.Config
	f, err := conf.ParseFile("<input>", httpEx)
	if err != nil {
	log.Fatal(err)
	}
	conf.CreateFromFiles(f.Name.Name, f)

	lprog, err := conf.Load()
	if err != nil {
	log.Fatalf("test 'package %s': Load: %s", f.Name.Name, err)
	}
	prog = ssautil.CreateProgram(lprog, ssa.InstantiateGenerics)
	prog.Build()

	main = prog.Package(lprog.Created[0].Pkg).Members["main"].(*ssa.Function)
	})
	return prog, main
	}

	var stats bool = false // print stats?

	func logStats(b testing.B, cnd bool, name string, cg callgraph.Graph, main *ssa.Function) {
	if cnd && stats {
	e := 0
	for _, n := range cg.Nodes {
	e += len(n.Out)
	}
	r := len(reaches(main, cg, false))
	b.Logf("%s:\t%d nodes\t%d edges\t%d reachable", name, len(cg.Nodes), e, r)
	}
	}

	func BenchmarkStatic(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	cg := static.CallGraph(prog)
	logStats(b, i == 0, "static", cg, main)
	}
	}

	func BenchmarkCHA(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	cg := cha.CallGraph(prog)
	logStats(b, i == 0, "cha", cg, main)
	}
	}

	func BenchmarkRTA(b *testing.B) {
	b.StopTimer()
	_, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	res := rta.Analyze([]*ssa.Function{main}, true)
	cg := res.CallGraph
	logStats(b, i == 0, "rta", cg, main)
	}
	}

	func BenchmarkPTA(b *testing.B) {
	b.StopTimer()
	_, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	config := &pointer.Config{Mains: []*ssa.Package{main.Pkg}, BuildCallGraph: true}
	res, err := pointer.Analyze(config)
	if err != nil {
	b.Fatal(err)
	}
	logStats(b, i == 0, "pta", res.CallGraph, main)
	}
	}

	func BenchmarkVTA(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	cg := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
	logStats(b, i == 0, "vta", cg, main)
	}
	}

	func BenchmarkVTA2(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	vta1 := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
	cg := vta.CallGraph(reaches(main, vta1, true), vta1)
	logStats(b, i == 0, "vta2", cg, main)
	}
	}

	func BenchmarkVTA3(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	vta1 := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
	vta2 := vta.CallGraph(reaches(main, vta1, true), vta1)
	cg := vta.CallGraph(reaches(main, vta2, true), vta2)
	logStats(b, i == 0, "vta3", cg, main)
	}
	}

	func BenchmarkVTAAlt(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	cha := cha.CallGraph(prog)
	cg := vta.CallGraph(reaches(main, cha, true), cha) // start from only functions reachable by CHA.
	logStats(b, i == 0, "vta-alt", cg, main)
	}
	}

	func BenchmarkVTAAlt2(b *testing.B) {
	b.StopTimer()
	prog, main := example()
	b.StartTimer()

	for i := 0; i < b.N; i++ {
	cha := cha.CallGraph(prog)
	vta1 := vta.CallGraph(reaches(main, cha, true), cha)
	cg := vta.CallGraph(reaches(main, vta1, true), vta1)
	logStats(b, i == 0, "vta-alt2", cg, main)
	}
	}

	// reaches computes the transitive closure of functions forward reachable
	// via calls in cg starting from `sources`. If refs is true, include
	// functions referred to in an instruction.
	func reaches(source ssa.Function, cg callgraph.Graph, refs bool) map[*ssa.Function]bool {
	seen := make(map[*ssa.Function]bool)
	var visit func(f *ssa.Function)
	visit = func(f *ssa.Function) {
	if seen[f] {
	return
	}
	seen[f] = true

	if n := cg.Nodes[f]; n != nil {
	for _, e := range n.Out {
	if e.Site != nil {
	visit(e.Callee.Func)
	}
	}
	}

	if refs {
	var buf [10]*ssa.Value // avoid alloc in common case
	for _, b := range f.Blocks {
	for _, instr := range b.Instrs {
	for _, op := range instr.Operands(buf[:0]) {
	if fn, ok := (op).(ssa.Function); ok {
	visit(fn)
	}
	}
	}
	}
	}
	}
	visit(source)
	return seen
	}