1 // Copyright 2013 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 ssautil // import "golang.org/x/tools/go/ssa/ssautil" 6 7 import ( 8 "go/ast" 9 "go/types" 10 11 "golang.org/x/tools/go/ssa" 12 13 _ "unsafe" // for linkname hack 14 ) 15 16 // This file defines utilities for visiting the SSA representation of 17 // a Program. 18 // 19 // TODO(adonovan): test coverage. 20 21 // AllFunctions finds and returns the set of functions potentially 22 // needed by program prog, as determined by a simple linker-style 23 // reachability algorithm starting from the members and method-sets of 24 // each package. The result may include anonymous functions and 25 // synthetic wrappers. 26 // 27 // Precondition: all packages are built. 28 // 29 // TODO(adonovan): this function is underspecified. It doesn't 30 // actually work like a linker, which computes reachability from main 31 // using something like go/callgraph/cha (without materializing the 32 // call graph). In fact, it treats all public functions and all 33 // methods of public non-parameterized types as roots, even though 34 // they may be unreachable--but only in packages created from syntax. 35 // 36 // I think we should deprecate AllFunctions function in favor of two 37 // clearly defined ones: 38 // 39 // 1. The first would efficiently compute CHA reachability from a set 40 // of main packages, making it suitable for a whole-program 41 // analysis context with InstantiateGenerics, in conjunction with 42 // Program.Build. 43 // 44 // 2. The second would return only the set of functions corresponding 45 // to source Func{Decl,Lit} syntax, like SrcFunctions in 46 // go/analysis/passes/buildssa; this is suitable for 47 // package-at-a-time (or handful of packages) context. 48 // ssa.Package could easily expose it as a field. 49 // 50 // We could add them unexported for now and use them via the linkname hack. 51 func AllFunctions(prog *ssa.Program) map[*ssa.Function]bool { 52 seen := make(map[*ssa.Function]bool) 53 54 var function func(fn *ssa.Function) 55 function = func(fn *ssa.Function) { 56 if !seen[fn] { 57 seen[fn] = true 58 var buf [10]*ssa.Value // avoid alloc in common case 59 for _, b := range fn.Blocks { 60 for _, instr := range b.Instrs { 61 for _, op := range instr.Operands(buf[:0]) { 62 if fn, ok := (*op).(*ssa.Function); ok { 63 function(fn) 64 } 65 } 66 } 67 } 68 } 69 } 70 71 // TODO(adonovan): opt: provide a way to share a builder 72 // across a sequence of MethodValue calls. 73 74 methodsOf := func(T types.Type) { 75 if !types.IsInterface(T) { 76 mset := prog.MethodSets.MethodSet(T) 77 for i := 0; i < mset.Len(); i++ { 78 function(prog.MethodValue(mset.At(i))) 79 } 80 } 81 } 82 83 // Historically, Program.RuntimeTypes used to include the type 84 // of any exported member of a package loaded from syntax that 85 // has a non-parameterized type, plus all types 86 // reachable from that type using reflection, even though 87 // these runtime types may not be required for them. 88 // 89 // Rather than break existing programs that rely on 90 // AllFunctions visiting extra methods that are unreferenced 91 // by IR and unreachable via reflection, we moved the logic 92 // here, unprincipled though it is. 93 // (See doc comment for better ideas.) 94 // 95 // Nonetheless, after the move, we no longer visit every 96 // method of any type recursively reachable from T, only the 97 // methods of T and *T themselves, and we only apply this to 98 // named types T, and not to the type of every exported 99 // package member. 100 exportedTypeHack := func(t *ssa.Type) { 101 if isSyntactic(t.Package()) && 102 ast.IsExported(t.Name()) && 103 !types.IsInterface(t.Type()) { 104 // Consider only named types. 105 // (Ignore aliases and unsafe.Pointer.) 106 if named, ok := t.Type().(*types.Named); ok { 107 if named.TypeParams() == nil { 108 methodsOf(named) // T 109 methodsOf(types.NewPointer(named)) // *T 110 } 111 } 112 } 113 } 114 115 for _, pkg := range prog.AllPackages() { 116 for _, mem := range pkg.Members { 117 switch mem := mem.(type) { 118 case *ssa.Function: 119 // Visit all package-level declared functions. 120 function(mem) 121 122 case *ssa.Type: 123 exportedTypeHack(mem) 124 } 125 } 126 } 127 128 // Visit all methods of types for which runtime types were 129 // materialized, as they are reachable through reflection. 130 for _, T := range prog.RuntimeTypes() { 131 methodsOf(T) 132 } 133 134 return seen 135 } 136 137 // MainPackages returns the subset of the specified packages 138 // named "main" that define a main function. 139 // The result may include synthetic "testmain" packages. 140 func MainPackages(pkgs []*ssa.Package) []*ssa.Package { 141 var mains []*ssa.Package 142 for _, pkg := range pkgs { 143 if pkg.Pkg.Name() == "main" && pkg.Func("main") != nil { 144 mains = append(mains, pkg) 145 } 146 } 147 return mains 148 } 149 150 // TODO(adonovan): propose a principled API for this. One possibility 151 // is a new field, Package.SrcFunctions []*Function, which would 152 // contain the list of SrcFunctions described in point 2 of the 153 // AllFunctions doc comment, or nil if the package is not from syntax. 154 // But perhaps overloading nil vs empty slice is too subtle. 155 // 156 //go:linkname isSyntactic golang.org/x/tools/go/ssa.isSyntactic 157 func isSyntactic(pkg *ssa.Package) bool 158