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  	"cmp"
    12  	"encoding/json"
    13  	"fmt"
    14  	"internal/buildcfg"
    15  	"io"
    16  	"os"
    17  	"path/filepath"
    18  	"slices"
    19  	"strings"
    20  )
    21  
    22  const (
    23  	debugTraceFuncs = 1 << iota
    24  	debugTraceFuncFlags
    25  	debugTraceResults
    26  	debugTraceParams
    27  	debugTraceExprClassify
    28  	debugTraceCalls
    29  	debugTraceScoring
    30  )
    31  
    32  // propAnalyzer interface is used for defining one or more analyzer
    33  // helper objects, each tasked with computing some specific subset of
    34  // the properties we're interested in. The assumption is that
    35  // properties are independent, so each new analyzer that implements
    36  // this interface can operate entirely on its own. For a given analyzer
    37  // there will be a sequence of calls to nodeVisitPre and nodeVisitPost
    38  // as the nodes within a function are visited, then a followup call to
    39  // setResults so that the analyzer can transfer its results into the
    40  // final properties object.
    41  type propAnalyzer interface {
    42  	nodeVisitPre(n ir.Node)
    43  	nodeVisitPost(n ir.Node)
    44  	setResults(funcProps *FuncProps)
    45  }
    46  
    47  // fnInlHeur contains inline heuristics state information about a
    48  // specific Go function being analyzed/considered by the inliner. Note
    49  // that in addition to constructing a fnInlHeur object by analyzing a
    50  // specific *ir.Func, there is also code in the test harness
    51  // (funcprops_test.go) that builds up fnInlHeur's by reading in and
    52  // parsing a dump. This is the reason why we have file/fname/line
    53  // fields below instead of just an *ir.Func field.
    54  type fnInlHeur struct {
    55  	props *FuncProps
    56  	cstab CallSiteTab
    57  	fname string
    58  	file  string
    59  	line  uint
    60  }
    61  
    62  var fpmap = map[*ir.Func]fnInlHeur{}
    63  
    64  // AnalyzeFunc computes function properties for fn and its contained
    65  // closures, updating the global 'fpmap' table. It is assumed that
    66  // "CanInline" has been run on fn and on the closures that feed
    67  // directly into calls; other closures not directly called will also
    68  // be checked inlinability for inlinability here in case they are
    69  // returned as a result.
    70  func AnalyzeFunc(fn *ir.Func, canInline func(*ir.Func), budgetForFunc func(*ir.Func) int32, inlineMaxBudget int) {
    71  	if fpmap == nil {
    72  		// If fpmap is nil this indicates that the main inliner pass is
    73  		// complete and we're doing inlining of wrappers (no heuristics
    74  		// used here).
    75  		return
    76  	}
    77  	if fn.OClosure != nil {
    78  		// closures will be processed along with their outer enclosing func.
    79  		return
    80  	}
    81  	enableDebugTraceIfEnv()
    82  	if debugTrace&debugTraceFuncs != 0 {
    83  		fmt.Fprintf(os.Stderr, "=-= AnalyzeFunc(%v)\n", fn)
    84  	}
    85  	// Build up a list containing 'fn' and any closures it contains. Along
    86  	// the way, test to see whether each closure is inlinable in case
    87  	// we might be returning it.
    88  	funcs := []*ir.Func{fn}
    89  	ir.VisitFuncAndClosures(fn, func(n ir.Node) {
    90  		if clo, ok := n.(*ir.ClosureExpr); ok {
    91  			funcs = append(funcs, clo.Func)
    92  		}
    93  	})
    94  
    95  	// Analyze the list of functions. We want to visit a given func
    96  	// only after the closures it contains have been processed, so
    97  	// iterate through the list in reverse order. Once a function has
    98  	// been analyzed, revisit the question of whether it should be
    99  	// inlinable; if it is over the default hairiness limit and it
   100  	// doesn't have any interesting properties, then we don't want
   101  	// the overhead of writing out its inline body.
   102  	nameFinder := newNameFinder(fn)
   103  	for i := len(funcs) - 1; i >= 0; i-- {
   104  		f := funcs[i]
   105  		if f.OClosure != nil && !f.InlinabilityChecked() {
   106  			canInline(f)
   107  		}
   108  		funcProps := analyzeFunc(f, inlineMaxBudget, nameFinder)
   109  		revisitInlinability(f, funcProps, budgetForFunc)
   110  		if f.Inl != nil {
   111  			f.Inl.Properties = funcProps.SerializeToString()
   112  		}
   113  	}
   114  	disableDebugTrace()
   115  }
   116  
   117  // TearDown is invoked at the end of the main inlining pass; doing
   118  // function analysis and call site scoring is unlikely to help a lot
   119  // after this point, so nil out fpmap and other globals to reclaim
   120  // storage.
   121  func TearDown() {
   122  	fpmap = nil
   123  	scoreCallsCache.tab = nil
   124  	scoreCallsCache.csl = nil
   125  }
   126  
   127  func analyzeFunc(fn *ir.Func, inlineMaxBudget int, nf *nameFinder) *FuncProps {
   128  	if funcInlHeur, ok := fpmap[fn]; ok {
   129  		return funcInlHeur.props
   130  	}
   131  	funcProps, fcstab := computeFuncProps(fn, inlineMaxBudget, nf)
   132  	file, line := fnFileLine(fn)
   133  	entry := fnInlHeur{
   134  		fname: fn.Sym().Name,
   135  		file:  file,
   136  		line:  line,
   137  		props: funcProps,
   138  		cstab: fcstab,
   139  	}
   140  	fn.SetNeverReturns(entry.props.Flags&FuncPropNeverReturns != 0)
   141  	fpmap[fn] = entry
   142  	if fn.Inl != nil && fn.Inl.Properties == "" {
   143  		fn.Inl.Properties = entry.props.SerializeToString()
   144  	}
   145  	return funcProps
   146  }
   147  
   148  // revisitInlinability revisits the question of whether to continue to
   149  // treat function 'fn' as an inline candidate based on the set of
   150  // properties we've computed for it. If (for example) it has an
   151  // initial size score of 150 and no interesting properties to speak
   152  // of, then there isn't really any point to moving ahead with it as an
   153  // inline candidate.
   154  func revisitInlinability(fn *ir.Func, funcProps *FuncProps, budgetForFunc func(*ir.Func) int32) {
   155  	if fn.Inl == nil {
   156  		return
   157  	}
   158  	maxAdj := int32(LargestNegativeScoreAdjustment(fn, funcProps))
   159  	budget := budgetForFunc(fn)
   160  	if fn.Inl.Cost+maxAdj > budget {
   161  		fn.Inl = nil
   162  	}
   163  }
   164  
   165  // computeFuncProps examines the Go function 'fn' and computes for it
   166  // a function "properties" object, to be used to drive inlining
   167  // heuristics. See comments on the FuncProps type for more info.
   168  func computeFuncProps(fn *ir.Func, inlineMaxBudget int, nf *nameFinder) (*FuncProps, CallSiteTab) {
   169  	if debugTrace&debugTraceFuncs != 0 {
   170  		fmt.Fprintf(os.Stderr, "=-= starting analysis of func %v:\n%+v\n",
   171  			fn, fn)
   172  	}
   173  	funcProps := new(FuncProps)
   174  	ffa := makeFuncFlagsAnalyzer(fn)
   175  	analyzers := []propAnalyzer{ffa}
   176  	analyzers = addResultsAnalyzer(fn, analyzers, funcProps, inlineMaxBudget, nf)
   177  	analyzers = addParamsAnalyzer(fn, analyzers, funcProps, nf)
   178  	runAnalyzersOnFunction(fn, analyzers)
   179  	for _, a := range analyzers {
   180  		a.setResults(funcProps)
   181  	}
   182  	cstab := computeCallSiteTable(fn, fn.Body, nil, ffa.panicPathTable(), 0, nf)
   183  	return funcProps, cstab
   184  }
   185  
   186  func runAnalyzersOnFunction(fn *ir.Func, analyzers []propAnalyzer) {
   187  	var doNode func(ir.Node) bool
   188  	doNode = func(n ir.Node) bool {
   189  		for _, a := range analyzers {
   190  			a.nodeVisitPre(n)
   191  		}
   192  		ir.DoChildren(n, doNode)
   193  		for _, a := range analyzers {
   194  			a.nodeVisitPost(n)
   195  		}
   196  		return false
   197  	}
   198  	doNode(fn)
   199  }
   200  
   201  func propsForFunc(fn *ir.Func) *FuncProps {
   202  	if funcInlHeur, ok := fpmap[fn]; ok {
   203  		return funcInlHeur.props
   204  	} else if fn.Inl != nil && fn.Inl.Properties != "" {
   205  		// FIXME: considering adding some sort of cache or table
   206  		// for deserialized properties of imported functions.
   207  		return DeserializeFromString(fn.Inl.Properties)
   208  	}
   209  	return nil
   210  }
   211  
   212  func fnFileLine(fn *ir.Func) (string, uint) {
   213  	p := base.Ctxt.InnermostPos(fn.Pos())
   214  	return filepath.Base(p.Filename()), p.Line()
   215  }
   216  
   217  func Enabled() bool {
   218  	return buildcfg.Experiment.NewInliner || UnitTesting()
   219  }
   220  
   221  func UnitTesting() bool {
   222  	return base.Debug.DumpInlFuncProps != "" ||
   223  		base.Debug.DumpInlCallSiteScores != 0
   224  }
   225  
   226  // DumpFuncProps computes and caches function properties for the func
   227  // 'fn', writing out a description of the previously computed set of
   228  // properties to the file given in 'dumpfile'. Used for the
   229  // "-d=dumpinlfuncprops=..." command line flag, intended for use
   230  // primarily in unit testing.
   231  func DumpFuncProps(fn *ir.Func, dumpfile string) {
   232  	if fn != nil {
   233  		if fn.OClosure != nil {
   234  			// closures will be processed along with their outer enclosing func.
   235  			return
   236  		}
   237  		captureFuncDumpEntry(fn)
   238  		ir.VisitFuncAndClosures(fn, func(n ir.Node) {
   239  			if clo, ok := n.(*ir.ClosureExpr); ok {
   240  				captureFuncDumpEntry(clo.Func)
   241  			}
   242  		})
   243  	} else {
   244  		emitDumpToFile(dumpfile)
   245  	}
   246  }
   247  
   248  // emitDumpToFile writes out the buffer function property dump entries
   249  // to a file, for unit testing. Dump entries need to be sorted by
   250  // definition line, and due to generics we need to account for the
   251  // possibility that several ir.Func's will have the same def line.
   252  func emitDumpToFile(dumpfile string) {
   253  	mode := os.O_WRONLY | os.O_CREATE | os.O_TRUNC
   254  	if dumpfile[0] == '+' {
   255  		dumpfile = dumpfile[1:]
   256  		mode = os.O_WRONLY | os.O_APPEND | os.O_CREATE
   257  	}
   258  	if dumpfile[0] == '%' {
   259  		dumpfile = dumpfile[1:]
   260  		d, b := filepath.Dir(dumpfile), filepath.Base(dumpfile)
   261  		ptag := strings.ReplaceAll(types.LocalPkg.Path, "/", ":")
   262  		dumpfile = d + "/" + ptag + "." + b
   263  	}
   264  	outf, err := os.OpenFile(dumpfile, mode, 0644)
   265  	if err != nil {
   266  		base.Fatalf("opening function props dump file %q: %v\n", dumpfile, err)
   267  	}
   268  	defer outf.Close()
   269  	dumpFilePreamble(outf)
   270  
   271  	atline := map[uint]uint{}
   272  	sl := make([]fnInlHeur, 0, len(dumpBuffer))
   273  	for _, e := range dumpBuffer {
   274  		sl = append(sl, e)
   275  		atline[e.line] = atline[e.line] + 1
   276  	}
   277  	sl = sortFnInlHeurSlice(sl)
   278  
   279  	prevline := uint(0)
   280  	for _, entry := range sl {
   281  		idx := uint(0)
   282  		if prevline == entry.line {
   283  			idx++
   284  		}
   285  		prevline = entry.line
   286  		atl := atline[entry.line]
   287  		if err := dumpFnPreamble(outf, &entry, nil, idx, atl); err != nil {
   288  			base.Fatalf("function props dump: %v\n", err)
   289  		}
   290  	}
   291  	dumpBuffer = nil
   292  }
   293  
   294  // captureFuncDumpEntry grabs the function properties object for 'fn'
   295  // and enqueues it for later dumping. Used for the
   296  // "-d=dumpinlfuncprops=..." command line flag, intended for use
   297  // primarily in unit testing.
   298  func captureFuncDumpEntry(fn *ir.Func) {
   299  	// avoid capturing compiler-generated equality funcs.
   300  	if strings.HasPrefix(fn.Sym().Name, ".eq.") {
   301  		return
   302  	}
   303  	funcInlHeur, ok := fpmap[fn]
   304  	if !ok {
   305  		// Missing entry is expected for functions that are too large
   306  		// to inline. We still want to write out call site scores in
   307  		// this case however.
   308  		funcInlHeur = fnInlHeur{cstab: callSiteTab}
   309  	}
   310  	if dumpBuffer == nil {
   311  		dumpBuffer = make(map[*ir.Func]fnInlHeur)
   312  	}
   313  	if _, ok := dumpBuffer[fn]; ok {
   314  		return
   315  	}
   316  	if debugTrace&debugTraceFuncs != 0 {
   317  		fmt.Fprintf(os.Stderr, "=-= capturing dump for %v:\n", fn)
   318  	}
   319  	dumpBuffer[fn] = funcInlHeur
   320  }
   321  
   322  // dumpFilePreamble writes out a file-level preamble for a given
   323  // Go function as part of a function properties dump.
   324  func dumpFilePreamble(w io.Writer) {
   325  	fmt.Fprintf(w, "// DO NOT EDIT (use 'go test -v -update-expected' instead.)\n")
   326  	fmt.Fprintf(w, "// See cmd/compile/internal/inline/inlheur/testdata/props/README.txt\n")
   327  	fmt.Fprintf(w, "// for more information on the format of this file.\n")
   328  	fmt.Fprintf(w, "// %s\n", preambleDelimiter)
   329  }
   330  
   331  // dumpFnPreamble writes out a function-level preamble for a given
   332  // Go function as part of a function properties dump. See the
   333  // README.txt file in testdata/props for more on the format of
   334  // this preamble.
   335  func dumpFnPreamble(w io.Writer, funcInlHeur *fnInlHeur, ecst encodedCallSiteTab, idx, atl uint) error {
   336  	fmt.Fprintf(w, "// %s %s %d %d %d\n",
   337  		funcInlHeur.file, funcInlHeur.fname, funcInlHeur.line, idx, atl)
   338  	// emit props as comments, followed by delimiter
   339  	fmt.Fprintf(w, "%s// %s\n", funcInlHeur.props.ToString("// "), comDelimiter)
   340  	data, err := json.Marshal(funcInlHeur.props)
   341  	if err != nil {
   342  		return fmt.Errorf("marshal error %v\n", err)
   343  	}
   344  	fmt.Fprintf(w, "// %s\n", string(data))
   345  	dumpCallSiteComments(w, funcInlHeur.cstab, ecst)
   346  	fmt.Fprintf(w, "// %s\n", fnDelimiter)
   347  	return nil
   348  }
   349  
   350  // sortFnInlHeurSlice sorts a slice of fnInlHeur based on
   351  // the starting line of the function definition, then by name.
   352  func sortFnInlHeurSlice(sl []fnInlHeur) []fnInlHeur {
   353  	slices.SortStableFunc(sl, func(a, b fnInlHeur) int {
   354  		if a.line != b.line {
   355  			return cmp.Compare(a.line, b.line)
   356  		}
   357  		return strings.Compare(a.fname, b.fname)
   358  	})
   359  	return sl
   360  }
   361  
   362  // delimiters written to various preambles to make parsing of
   363  // dumps easier.
   364  const preambleDelimiter = "<endfilepreamble>"
   365  const fnDelimiter = "<endfuncpreamble>"
   366  const comDelimiter = "<endpropsdump>"
   367  const csDelimiter = "<endcallsites>"
   368  
   369  // dumpBuffer stores up function properties dumps when
   370  // "-d=dumpinlfuncprops=..." is in effect.
   371  var dumpBuffer map[*ir.Func]fnInlHeur
   372
View as plain text