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