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