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