callgraph_test.go

Documentation: golang.org/x/tools/go/callgraph

     1  // Copyright 2023 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  package callgraph_test
     5  
     6  import (
     7  	"log"
     8  	"sync"
     9  	"testing"
    10  
    11  	"golang.org/x/tools/go/callgraph"
    12  	"golang.org/x/tools/go/callgraph/cha"
    13  	"golang.org/x/tools/go/callgraph/rta"
    14  	"golang.org/x/tools/go/callgraph/static"
    15  	"golang.org/x/tools/go/callgraph/vta"
    16  	"golang.org/x/tools/go/loader"
    17  	"golang.org/x/tools/go/ssa"
    18  	"golang.org/x/tools/go/ssa/ssautil"
    19  )
    20  
    21  // Benchmarks comparing different callgraph algorithms implemented in
    22  // x/tools/go/callgraph. Comparison is on both speed, memory and precision.
    23  // Fewer edges and fewer reachable nodes implies a more precise result.
    24  // Comparison is done on a hello world http server using net/http.
    25  //
    26  // Current results were on an i7 macbook on go version devel go1.20-2730.
    27  // Number of nodes, edges, and reachable function are expected to vary between
    28  // go versions. Timing results are expected to vary between machines.
    29  // BenchmarkStatic-12	 53 ms/op     6 MB/op	12113 nodes	 37355 edges	1522 reachable
    30  // BenchmarkCHA-12    	 86 ms/op	 16 MB/op	12113 nodes	131717 edges	7640 reachable
    31  // BenchmarkRTA-12		110 ms/op	 12 MB/op	 6566 nodes	 42291 edges	5099 reachable
    32  // BenchmarkPTA-12	   1427 ms/op	600 MB/op	 8714 nodes	 28244 edges	4184 reachable
    33  // BenchmarkVTA-12		600 ms/op	 78 MB/op	12114 nodes	 44861 edges	4919 reachable
    34  // BenchmarkVTA2-12		793 ms/op	104 MB/op	 5450 nodes	 22208 edges	4042 reachable
    35  // BenchmarkVTA3-12		977 ms/op	124 MB/op	 4621 nodes	 19331 edges	3700 reachable
    36  // BenchmarkVTAAlt-12	372 ms/op	 57 MB/op	 7763 nodes	 29912 edges	4258 reachable
    37  // BenchmarkVTAAlt2-12	570 ms/op	 78 MB/op	 4838 nodes	 20169 edges	3737 reachable
    38  //
    39  // Note:
    40  // * Static is unsound and may miss real edges.
    41  // * RTA starts from a main function and only includes reachable functions.
    42  // * CHA starts from all functions.
    43  // * VTA, VTA2, and VTA3 are starting from all functions and the CHA callgraph.
    44  //   VTA2 and VTA3 are the result of re-applying VTA to the functions reachable
    45  //   from main() via the callgraph of the previous stage.
    46  // * VTAAlt, and VTAAlt2 start from the functions reachable from main via the
    47  //   CHA callgraph.
    48  // * All algorithms are unsound w.r.t. reflection.
    49  
    50  const httpEx = `package main
    51  
    52  import (
    53      "fmt"
    54      "net/http"
    55  )
    56  
    57  func hello(w http.ResponseWriter, req *http.Request) {
    58      fmt.Fprintf(w, "hello world\n")
    59  }
    60  
    61  func main() {
    62      http.HandleFunc("/hello", hello)
    63      http.ListenAndServe(":8090", nil)
    64  }
    65  `
    66  
    67  var (
    68  	once sync.Once
    69  	prog *ssa.Program
    70  	main *ssa.Function
    71  )
    72  
    73  func example() (*ssa.Program, *ssa.Function) {
    74  	once.Do(func() {
    75  		var conf loader.Config
    76  		f, err := conf.ParseFile("<input>", httpEx)
    77  		if err != nil {
    78  			log.Fatal(err)
    79  		}
    80  		conf.CreateFromFiles(f.Name.Name, f)
    81  
    82  		lprog, err := conf.Load()
    83  		if err != nil {
    84  			log.Fatalf("test 'package %s': Load: %s", f.Name.Name, err)
    85  		}
    86  		prog = ssautil.CreateProgram(lprog, ssa.InstantiateGenerics)
    87  		prog.Build()
    88  
    89  		main = prog.Package(lprog.Created[0].Pkg).Members["main"].(*ssa.Function)
    90  	})
    91  	return prog, main
    92  }
    93  
    94  var stats bool = false // print stats?
    95  
    96  func logStats(b *testing.B, cnd bool, name string, cg *callgraph.Graph, main *ssa.Function) {
    97  	if cnd && stats {
    98  		e := 0
    99  		for _, n := range cg.Nodes {
   100  			e += len(n.Out)
   101  		}
   102  		r := len(reaches(main, cg, false))
   103  		b.Logf("%s:\t%d nodes\t%d edges\t%d reachable", name, len(cg.Nodes), e, r)
   104  	}
   105  }
   106  
   107  func BenchmarkStatic(b *testing.B) {
   108  	b.StopTimer()
   109  	prog, main := example()
   110  	b.StartTimer()
   111  
   112  	for i := 0; i < b.N; i++ {
   113  		cg := static.CallGraph(prog)
   114  		logStats(b, i == 0, "static", cg, main)
   115  	}
   116  }
   117  
   118  func BenchmarkCHA(b *testing.B) {
   119  	b.StopTimer()
   120  	prog, main := example()
   121  	b.StartTimer()
   122  
   123  	for i := 0; i < b.N; i++ {
   124  		cg := cha.CallGraph(prog)
   125  		logStats(b, i == 0, "cha", cg, main)
   126  	}
   127  }
   128  
   129  func BenchmarkRTA(b *testing.B) {
   130  	b.StopTimer()
   131  	_, main := example()
   132  	b.StartTimer()
   133  
   134  	for i := 0; i < b.N; i++ {
   135  		res := rta.Analyze([]*ssa.Function{main}, true)
   136  		cg := res.CallGraph
   137  		logStats(b, i == 0, "rta", cg, main)
   138  	}
   139  }
   140  
   141  func BenchmarkVTA(b *testing.B) {
   142  	b.StopTimer()
   143  	prog, main := example()
   144  	b.StartTimer()
   145  
   146  	for i := 0; i < b.N; i++ {
   147  		cg := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
   148  		logStats(b, i == 0, "vta", cg, main)
   149  	}
   150  }
   151  
   152  func BenchmarkVTA2(b *testing.B) {
   153  	b.StopTimer()
   154  	prog, main := example()
   155  	b.StartTimer()
   156  
   157  	for i := 0; i < b.N; i++ {
   158  		vta1 := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
   159  		cg := vta.CallGraph(reaches(main, vta1, true), vta1)
   160  		logStats(b, i == 0, "vta2", cg, main)
   161  	}
   162  }
   163  
   164  func BenchmarkVTA3(b *testing.B) {
   165  	b.StopTimer()
   166  	prog, main := example()
   167  	b.StartTimer()
   168  
   169  	for i := 0; i < b.N; i++ {
   170  		vta1 := vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
   171  		vta2 := vta.CallGraph(reaches(main, vta1, true), vta1)
   172  		cg := vta.CallGraph(reaches(main, vta2, true), vta2)
   173  		logStats(b, i == 0, "vta3", cg, main)
   174  	}
   175  }
   176  
   177  func BenchmarkVTAAlt(b *testing.B) {
   178  	b.StopTimer()
   179  	prog, main := example()
   180  	b.StartTimer()
   181  
   182  	for i := 0; i < b.N; i++ {
   183  		cha := cha.CallGraph(prog)
   184  		cg := vta.CallGraph(reaches(main, cha, true), cha) // start from only functions reachable by CHA.
   185  		logStats(b, i == 0, "vta-alt", cg, main)
   186  	}
   187  }
   188  
   189  func BenchmarkVTAAlt2(b *testing.B) {
   190  	b.StopTimer()
   191  	prog, main := example()
   192  	b.StartTimer()
   193  
   194  	for i := 0; i < b.N; i++ {
   195  		cha := cha.CallGraph(prog)
   196  		vta1 := vta.CallGraph(reaches(main, cha, true), cha)
   197  		cg := vta.CallGraph(reaches(main, vta1, true), vta1)
   198  		logStats(b, i == 0, "vta-alt2", cg, main)
   199  	}
   200  }
   201  
   202  // reaches computes the transitive closure of functions forward reachable
   203  // via calls in cg starting from `sources`. If refs is true, include
   204  // functions referred to in an instruction.
   205  func reaches(source *ssa.Function, cg *callgraph.Graph, refs bool) map[*ssa.Function]bool {
   206  	seen := make(map[*ssa.Function]bool)
   207  	var visit func(f *ssa.Function)
   208  	visit = func(f *ssa.Function) {
   209  		if seen[f] {
   210  			return
   211  		}
   212  		seen[f] = true
   213  
   214  		if n := cg.Nodes[f]; n != nil {
   215  			for _, e := range n.Out {
   216  				if e.Site != nil {
   217  					visit(e.Callee.Func)
   218  				}
   219  			}
   220  		}
   221  
   222  		if refs {
   223  			var buf [10]*ssa.Value // avoid alloc in common case
   224  			for _, b := range f.Blocks {
   225  				for _, instr := range b.Instrs {
   226  					for _, op := range instr.Operands(buf[:0]) {
   227  						if fn, ok := (*op).(*ssa.Function); ok {
   228  							visit(fn)
   229  						}
   230  					}
   231  				}
   232  			}
   233  		}
   234  	}
   235  	visit(source)
   236  	return seen
   237  }
   238
View as plain text