src/cmd/compile/internal/inline/inlheur/analyze.go

   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
   5 package inlheur
   6
   7 import (
   8         "cmd/compile/internal/base"
   9         "cmd/compile/internal/ir"
  10         "encoding/json"
  11         "fmt"
  12         "internal/goexperiment"
  13         "io"
  14         "os"
  15         "path/filepath"
  16         "sort"
  17         "strings"
  18 )
  19
  20 const (
  21         debugTraceFuncs = 1 << iota
  22         debugTraceFuncFlags
  23         debugTraceResults
  24         debugTraceParams
  25         debugTraceExprClassify
  26 )
  27
  28 // propAnalyzer interface is used for defining one or more analyzer
  29 // helper objects, each tasked with computing some specific subset of
  30 // the properties we're interested in. The assumption is that
  31 // properties are independent, so each new analyzer that implements
  32 // this interface can operate entirely on its own. For a given analyzer
  33 // there will be a sequence of calls to nodeVisitPre and nodeVisitPost
  34 // as the nodes within a function are visited, then a followup call to
  35 // setResults so that the analyzer can transfer its results into the
  36 // final properties object.
  37 type propAnalyzer interface {
  38         nodeVisitPre(n ir.Node)
  39         nodeVisitPost(n ir.Node)
  40         setResults(fp *FuncProps)
  41 }
  42
  43 // fnInlHeur contains inline heuristics state information about
  44 // a specific Go function being analyzed/considered by the inliner.
  45 type fnInlHeur struct {
  46         fname string
  47         file  string
  48         line  uint
  49         props *FuncProps
  50 }
  51
  52 var fpmap = map[*ir.Func]fnInlHeur{}
  53
  54 func AnalyzeFunc(fn *ir.Func, canInline func(*ir.Func)) *FuncProps {
  55         if fih, ok := fpmap[fn]; ok {
  56                 return fih.props
  57         }
  58         fp := computeFuncProps(fn, canInline)
  59         file, line := fnFileLine(fn)
  60         entry := fnInlHeur{
  61                 fname: fn.Sym().Name,
  62                 file:  file,
  63                 line:  line,
  64                 props: fp,
  65         }
  66         fpmap[fn] = entry
  67         return fp
  68 }
  69
  70 // computeFuncProps examines the Go function 'fn' and computes for it
  71 // a function "properties" object, to be used to drive inlining
  72 // heuristics. See comments on the FuncProps type for more info.
  73 func computeFuncProps(fn *ir.Func, canInline func(*ir.Func)) *FuncProps {
  74         enableDebugTraceIfEnv()
  75         if debugTrace&debugTraceFuncs != 0 {
  76                 fmt.Fprintf(os.Stderr, "=-= starting analysis of func %v:\n%+v\n",
  77                         fn.Sym().Name, fn)
  78         }
  79         ra := makeResultsAnalyzer(fn, canInline)
  80         pa := makeParamsAnalyzer(fn)
  81         ffa := makeFuncFlagsAnalyzer(fn)
  82         analyzers := []propAnalyzer{ffa, ra, pa}
  83         fp := new(FuncProps)
  84         runAnalyzersOnFunction(fn, analyzers)
  85         for _, a := range analyzers {
  86                 a.setResults(fp)
  87         }
  88         disableDebugTrace()
  89         return fp
  90 }
  91
  92 func runAnalyzersOnFunction(fn *ir.Func, analyzers []propAnalyzer) {
  93         var doNode func(ir.Node) bool
  94         doNode = func(n ir.Node) bool {
  95                 for _, a := range analyzers {
  96                         a.nodeVisitPre(n)
  97                 }
  98                 ir.DoChildren(n, doNode)
  99                 for _, a := range analyzers {
 100                         a.nodeVisitPost(n)
 101                 }
 102                 return false
 103         }
 104         doNode(fn)
 105 }
 106
 107 func propsForFunc(fn *ir.Func) *FuncProps {
 108         if fih, ok := fpmap[fn]; ok {
 109                 return fih.props
 110         } else if fn.Inl != nil && fn.Inl.Properties != "" {
 111                 // FIXME: considering adding some sort of cache or table
 112                 // for deserialized properties of imported functions.
 113                 return DeserializeFromString(fn.Inl.Properties)
 114         }
 115         return nil
 116 }
 117
 118 func fnFileLine(fn *ir.Func) (string, uint) {
 119         p := base.Ctxt.InnermostPos(fn.Pos())
 120         return filepath.Base(p.Filename()), p.Line()
 121 }
 122
 123 func UnitTesting() bool {
 124         return base.Debug.DumpInlFuncProps != ""
 125 }
 126
 127 // DumpFuncProps computes and caches function properties for the func
 128 // 'fn', or if fn is nil, writes out the cached set of properties to
 129 // the file given in 'dumpfile'. Used for the "-d=dumpinlfuncprops=..."
 130 // command line flag, intended for use primarily in unit testing.
 131 func DumpFuncProps(fn *ir.Func, dumpfile string, canInline func(*ir.Func)) {
 132         if fn != nil {
 133                 captureFuncDumpEntry(fn, canInline)
 134         } else {
 135                 emitDumpToFile(dumpfile)
 136         }
 137 }
 138
 139 // emitDumpToFile writes out the buffer function property dump entries
 140 // to a file, for unit testing. Dump entries need to be sorted by
 141 // definition line, and due to generics we need to account for the
 142 // possibility that several ir.Func's will have the same def line.
 143 func emitDumpToFile(dumpfile string) {
 144         outf, err := os.OpenFile(dumpfile, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644)
 145         if err != nil {
 146                 base.Fatalf("opening function props dump file %q: %v\n", dumpfile, err)
 147         }
 148         defer outf.Close()
 149         dumpFilePreamble(outf)
 150
 151         atline := map[uint]uint{}
 152         sl := make([]fnInlHeur, 0, len(dumpBuffer))
 153         for _, e := range dumpBuffer {
 154                 sl = append(sl, e)
 155                 atline[e.line] = atline[e.line] + 1
 156         }
 157         sl = sortFnInlHeurSlice(sl)
 158
 159         prevline := uint(0)
 160         for _, entry := range sl {
 161                 idx := uint(0)
 162                 if prevline == entry.line {
 163                         idx++
 164                 }
 165                 prevline = entry.line
 166                 atl := atline[entry.line]
 167                 if err := dumpFnPreamble(outf, &entry, idx, atl); err != nil {
 168                         base.Fatalf("function props dump: %v\n", err)
 169                 }
 170         }
 171         dumpBuffer = nil
 172 }
 173
 174 // captureFuncDumpEntry analyzes function 'fn' and adds a entry
 175 // for it to 'dumpBuffer'. Used for unit testing.
 176 func captureFuncDumpEntry(fn *ir.Func, canInline func(*ir.Func)) {
 177         // avoid capturing compiler-generated equality funcs.
 178         if strings.HasPrefix(fn.Sym().Name, ".eq.") {
 179                 return
 180         }
 181         fih, ok := fpmap[fn]
 182         if goexperiment.NewInliner {
 183                 // Props object should already be present.
 184                 if !ok {
 185                         panic("unexpected missing props")
 186                 }
 187         } else {
 188                 AnalyzeFunc(fn, canInline)
 189                 fih = fpmap[fn]
 190                 if fn.Inl != nil && fn.Inl.Properties == "" {
 191                         fn.Inl.Properties = fih.props.SerializeToString()
 192                 }
 193         }
 194         if dumpBuffer == nil {
 195                 dumpBuffer = make(map[*ir.Func]fnInlHeur)
 196         }
 197         if _, ok := dumpBuffer[fn]; ok {
 198                 // we can wind up seeing closures multiple times here,
 199                 // so don't add them more than once.
 200                 return
 201         }
 202         dumpBuffer[fn] = fih
 203 }
 204
 205 // dumpFilePreamble writes out a file-level preamble for a given
 206 // Go function as part of a function properties dump.
 207 func dumpFilePreamble(w io.Writer) {
 208         fmt.Fprintf(w, "// DO NOT EDIT (use 'go test -v -update-expected' instead.)\n")
 209         fmt.Fprintf(w, "// See cmd/compile/internal/inline/inlheur/testdata/props/README.txt\n")
 210         fmt.Fprintf(w, "// for more information on the format of this file.\n")
 211         fmt.Fprintf(w, "// %s\n", preambleDelimiter)
 212 }
 213
 214 // dumpFilePreamble writes out a function-level preamble for a given
 215 // Go function as part of a function properties dump. See the
 216 // README.txt file in testdata/props for more on the format of
 217 // this preamble.
 218 func dumpFnPreamble(w io.Writer, fih *fnInlHeur, idx, atl uint) error {
 219         fmt.Fprintf(w, "// %s %s %d %d %d\n",
 220                 fih.file, fih.fname, fih.line, idx, atl)
 221         // emit props as comments, followed by delimiter
 222         fmt.Fprintf(w, "%s// %s\n", fih.props.ToString("// "), comDelimiter)
 223         data, err := json.Marshal(fih.props)
 224         if err != nil {
 225                 return fmt.Errorf("marshall error %v\n", err)
 226         }
 227         fmt.Fprintf(w, "// %s\n// %s\n", string(data), fnDelimiter)
 228         return nil
 229 }
 230
 231 // sortFnInlHeurSlice sorts a slice of fnInlHeur based on
 232 // the starting line of the function definition, then by name.
 233 func sortFnInlHeurSlice(sl []fnInlHeur) []fnInlHeur {
 234         sort.SliceStable(sl, func(i, j int) bool {
 235                 if sl[i].line != sl[j].line {
 236                         return sl[i].line < sl[j].line
 237                 }
 238                 return sl[i].fname < sl[j].fname
 239         })
 240         return sl
 241 }
 242
 243 // delimiters written to various preambles to make parsing of
 244 // dumps easier.
 245 const preambleDelimiter = "<endfilepreamble>"
 246 const fnDelimiter = "<endfuncpreamble>"
 247 const comDelimiter = "<endpropsdump>"
 248
 249 // dumpBuffer stores up function properties dumps when
 250 // "-d=dumpinlfuncprops=..." is in effect.
 251 var dumpBuffer map[*ir.Func]fnInlHeur