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