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