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         "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(funcProps *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         inlineMaxBudget int32
  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), inlineMaxBudget int32) *FuncProps {
  64         if funcInlHeur, ok := fpmap[fn]; ok {
  65                 return funcInlHeur.props
  66         }
  67         funcProps, fcstab := computeFuncProps(fn, canInline, inlineMaxBudget)
  68         file, line := fnFileLine(fn)
  69         entry := fnInlHeur{
  70                 fname:           fn.Sym().Name,
  71                 file:            file,
  72                 line:            line,
  73                 inlineMaxBudget: inlineMaxBudget,
  74                 props:           funcProps,
  75                 cstab:           fcstab,
  76         }
  77         fn.SetNeverReturns(entry.props.Flags&FuncPropNeverReturns != 0)
  78         fpmap[fn] = entry
  79         if fn.Inl != nil && fn.Inl.Properties == "" {
  80                 fn.Inl.Properties = entry.props.SerializeToString()
  81         }
  82         return funcProps
  83 }
  84
  85 // RevisitInlinability revisits the question of whether to continue to
  86 // treat function 'fn' as an inline candidate based on the set of
  87 // properties we've computed for it. If (for example) it has an
  88 // initial size score of 150 and no interesting properties to speak
  89 // of, then there isn't really any point to moving ahead with it as an
  90 // inline candidate.
  91 func RevisitInlinability(fn *ir.Func, budgetForFunc func(*ir.Func) int32) {
  92         if fn.Inl == nil {
  93                 return
  94         }
  95         entry, ok := fpmap[fn]
  96         if !ok {
  97                 //FIXME: issue error?
  98                 return
  99         }
 100         mxAdjust := int32(largestScoreAdjustment(fn, entry.props))
 101         budget := budgetForFunc(fn)
 102         if fn.Inl.Cost+mxAdjust > budget {
 103                 fn.Inl = nil
 104         }
 105 }
 106
 107 // computeFuncProps examines the Go function 'fn' and computes for it
 108 // a function "properties" object, to be used to drive inlining
 109 // heuristics. See comments on the FuncProps type for more info.
 110 func computeFuncProps(fn *ir.Func, canInline func(*ir.Func), inlineMaxBudget int32) (*FuncProps, CallSiteTab) {
 111         enableDebugTraceIfEnv()
 112         if debugTrace&debugTraceFuncs != 0 {
 113                 fmt.Fprintf(os.Stderr, "=-= starting analysis of func %v:\n%+v\n",
 114                         fn, fn)
 115         }
 116         ra := makeResultsAnalyzer(fn, canInline, inlineMaxBudget)
 117         pa := makeParamsAnalyzer(fn)
 118         ffa := makeFuncFlagsAnalyzer(fn)
 119         analyzers := []propAnalyzer{ffa, ra, pa}
 120         funcProps := new(FuncProps)
 121         runAnalyzersOnFunction(fn, analyzers)
 122         for _, a := range analyzers {
 123                 a.setResults(funcProps)
 124         }
 125         // Now build up a partial table of callsites for this func.
 126         cstab := computeCallSiteTable(fn, fn.Body, nil, ffa.panicPathTable(), 0)
 127         disableDebugTrace()
 128         return funcProps, cstab
 129 }
 130
 131 func runAnalyzersOnFunction(fn *ir.Func, analyzers []propAnalyzer) {
 132         var doNode func(ir.Node) bool
 133         doNode = func(n ir.Node) bool {
 134                 for _, a := range analyzers {
 135                         a.nodeVisitPre(n)
 136                 }
 137                 ir.DoChildren(n, doNode)
 138                 for _, a := range analyzers {
 139                         a.nodeVisitPost(n)
 140                 }
 141                 return false
 142         }
 143         doNode(fn)
 144 }
 145
 146 func propsForFunc(fn *ir.Func) *FuncProps {
 147         if funcInlHeur, ok := fpmap[fn]; ok {
 148                 return funcInlHeur.props
 149         } else if fn.Inl != nil && fn.Inl.Properties != "" {
 150                 // FIXME: considering adding some sort of cache or table
 151                 // for deserialized properties of imported functions.
 152                 return DeserializeFromString(fn.Inl.Properties)
 153         }
 154         return nil
 155 }
 156
 157 func fnFileLine(fn *ir.Func) (string, uint) {
 158         p := base.Ctxt.InnermostPos(fn.Pos())
 159         return filepath.Base(p.Filename()), p.Line()
 160 }
 161
 162 func UnitTesting() bool {
 163         return base.Debug.DumpInlFuncProps != "" ||
 164                 base.Debug.DumpInlCallSiteScores != 0
 165 }
 166
 167 // DumpFuncProps computes and caches function properties for the func
 168 // 'fn', writing out a description of the previously computed set of
 169 // properties to the file given in 'dumpfile'. Used for the
 170 // "-d=dumpinlfuncprops=..." command line flag, intended for use
 171 // primarily in unit testing.
 172 func DumpFuncProps(fn *ir.Func, dumpfile string, canInline func(*ir.Func), inlineMaxBudget int32) {
 173         if fn != nil {
 174                 enableDebugTraceIfEnv()
 175                 captureFuncDumpEntry(fn, canInline, inlineMaxBudget)
 176                 disableDebugTrace()
 177         } else {
 178                 emitDumpToFile(dumpfile)
 179         }
 180 }
 181
 182 // emitDumpToFile writes out the buffer function property dump entries
 183 // to a file, for unit testing. Dump entries need to be sorted by
 184 // definition line, and due to generics we need to account for the
 185 // possibility that several ir.Func's will have the same def line.
 186 func emitDumpToFile(dumpfile string) {
 187         mode := os.O_WRONLY | os.O_CREATE | os.O_TRUNC
 188         if dumpfile[0] == '+' {
 189                 dumpfile = dumpfile[1:]
 190                 mode = os.O_WRONLY | os.O_APPEND | os.O_CREATE
 191         }
 192         if dumpfile[0] == '%' {
 193                 dumpfile = dumpfile[1:]
 194                 d, b := filepath.Dir(dumpfile), filepath.Base(dumpfile)
 195                 ptag := strings.ReplaceAll(types.LocalPkg.Path, "/", ":")
 196                 dumpfile = d + "/" + ptag + "." + b
 197         }
 198         outf, err := os.OpenFile(dumpfile, mode, 0644)
 199         if err != nil {
 200                 base.Fatalf("opening function props dump file %q: %v\n", dumpfile, err)
 201         }
 202         defer outf.Close()
 203         dumpFilePreamble(outf)
 204
 205         atline := map[uint]uint{}
 206         sl := make([]fnInlHeur, 0, len(dumpBuffer))
 207         for _, e := range dumpBuffer {
 208                 sl = append(sl, e)
 209                 atline[e.line] = atline[e.line] + 1
 210         }
 211         sl = sortFnInlHeurSlice(sl)
 212
 213         prevline := uint(0)
 214         for _, entry := range sl {
 215                 idx := uint(0)
 216                 if prevline == entry.line {
 217                         idx++
 218                 }
 219                 prevline = entry.line
 220                 atl := atline[entry.line]
 221                 if err := dumpFnPreamble(outf, &entry, nil, idx, atl); err != nil {
 222                         base.Fatalf("function props dump: %v\n", err)
 223                 }
 224         }
 225         dumpBuffer = nil
 226 }
 227
 228 // captureFuncDumpEntry grabs the function properties object for 'fn'
 229 // and enqueues it for later dumping. Used for the
 230 // "-d=dumpinlfuncprops=..." command line flag, intended for use
 231 // primarily in unit testing.
 232 func captureFuncDumpEntry(fn *ir.Func, canInline func(*ir.Func), inlineMaxBudget int32) {
 233         // avoid capturing compiler-generated equality funcs.
 234         if strings.HasPrefix(fn.Sym().Name, ".eq.") {
 235                 return
 236         }
 237         funcInlHeur, ok := fpmap[fn]
 238         if !ok {
 239                 // Missing entry is expected for functions that are too large
 240                 // to inline. We still want to write out call site scores in
 241                 // this case however.
 242                 funcInlHeur = fnInlHeur{cstab: callSiteTab}
 243         }
 244         if dumpBuffer == nil {
 245                 dumpBuffer = make(map[*ir.Func]fnInlHeur)
 246         }
 247         if _, ok := dumpBuffer[fn]; ok {
 248                 // we can wind up seeing closures multiple times here,
 249                 // so don't add them more than once.
 250                 return
 251         }
 252         if debugTrace&debugTraceFuncs != 0 {
 253                 fmt.Fprintf(os.Stderr, "=-= capturing dump for %v:\n", fn)
 254         }
 255         dumpBuffer[fn] = funcInlHeur
 256 }
 257
 258 // dumpFilePreamble writes out a file-level preamble for a given
 259 // Go function as part of a function properties dump.
 260 func dumpFilePreamble(w io.Writer) {
 261         fmt.Fprintf(w, "// DO NOT EDIT (use 'go test -v -update-expected' instead.)\n")
 262         fmt.Fprintf(w, "// See cmd/compile/internal/inline/inlheur/testdata/props/README.txt\n")
 263         fmt.Fprintf(w, "// for more information on the format of this file.\n")
 264         fmt.Fprintf(w, "// %s\n", preambleDelimiter)
 265 }
 266
 267 // dumpFnPreamble writes out a function-level preamble for a given
 268 // Go function as part of a function properties dump. See the
 269 // README.txt file in testdata/props for more on the format of
 270 // this preamble.
 271 func dumpFnPreamble(w io.Writer, funcInlHeur *fnInlHeur, ecst encodedCallSiteTab, idx, atl uint) error {
 272         fmt.Fprintf(w, "// %s %s %d %d %d\n",
 273                 funcInlHeur.file, funcInlHeur.fname, funcInlHeur.line, idx, atl)
 274         // emit props as comments, followed by delimiter
 275         fmt.Fprintf(w, "%s// %s\n", funcInlHeur.props.ToString("// "), comDelimiter)
 276         data, err := json.Marshal(funcInlHeur.props)
 277         if err != nil {
 278                 return fmt.Errorf("marshall error %v\n", err)
 279         }
 280         fmt.Fprintf(w, "// %s\n", string(data))
 281         dumpCallSiteComments(w, funcInlHeur.cstab, ecst)
 282         fmt.Fprintf(w, "// %s\n", fnDelimiter)
 283         return nil
 284 }
 285
 286 // sortFnInlHeurSlice sorts a slice of fnInlHeur based on
 287 // the starting line of the function definition, then by name.
 288 func sortFnInlHeurSlice(sl []fnInlHeur) []fnInlHeur {
 289         sort.SliceStable(sl, func(i, j int) bool {
 290                 if sl[i].line != sl[j].line {
 291                         return sl[i].line < sl[j].line
 292                 }
 293                 return sl[i].fname < sl[j].fname
 294         })
 295         return sl
 296 }
 297
 298 // delimiters written to various preambles to make parsing of
 299 // dumps easier.
 300 const preambleDelimiter = "<endfilepreamble>"
 301 const fnDelimiter = "<endfuncpreamble>"
 302 const comDelimiter = "<endpropsdump>"
 303 const csDelimiter = "<endcallsites>"
 304
 305 // dumpBuffer stores up function properties dumps when
 306 // "-d=dumpinlfuncprops=..." is in effect.
 307 var dumpBuffer map[*ir.Func]fnInlHeur