pgo.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 devirtualize
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/inline"
    10  	"cmd/compile/internal/ir"
    11  	"cmd/compile/internal/logopt"
    12  	"cmd/compile/internal/pgoir"
    13  	"cmd/compile/internal/typecheck"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/obj"
    16  	"cmd/internal/src"
    17  	"encoding/json"
    18  	"fmt"
    19  	"os"
    20  	"strings"
    21  )
    22  
    23  // CallStat summarizes a single call site.
    24  //
    25  // This is used only for debug logging.
    26  type CallStat struct {
    27  	Pkg string // base.Ctxt.Pkgpath
    28  	Pos string // file:line:col of call.
    29  
    30  	Caller string // Linker symbol name of calling function.
    31  
    32  	// Direct or indirect call.
    33  	Direct bool
    34  
    35  	// For indirect calls, interface call or other indirect function call.
    36  	Interface bool
    37  
    38  	// Total edge weight from this call site.
    39  	Weight int64
    40  
    41  	// Hottest callee from this call site, regardless of type
    42  	// compatibility.
    43  	Hottest       string
    44  	HottestWeight int64
    45  
    46  	// Devirtualized callee if != "".
    47  	//
    48  	// Note that this may be different than Hottest because we apply
    49  	// type-check restrictions, which helps distinguish multiple calls on
    50  	// the same line.
    51  	Devirtualized       string
    52  	DevirtualizedWeight int64
    53  }
    54  
    55  // ProfileGuided performs call devirtualization of indirect calls based on
    56  // profile information.
    57  //
    58  // Specifically, it performs conditional devirtualization of interface calls or
    59  // function value calls for the hottest callee.
    60  //
    61  // That is, for interface calls it performs a transformation like:
    62  //
    63  //	type Iface interface {
    64  //		Foo()
    65  //	}
    66  //
    67  //	type Concrete struct{}
    68  //
    69  //	func (Concrete) Foo() {}
    70  //
    71  //	func foo(i Iface) {
    72  //		i.Foo()
    73  //	}
    74  //
    75  // to:
    76  //
    77  //	func foo(i Iface) {
    78  //		if c, ok := i.(Concrete); ok {
    79  //			c.Foo()
    80  //		} else {
    81  //			i.Foo()
    82  //		}
    83  //	}
    84  //
    85  // For function value calls it performs a transformation like:
    86  //
    87  //	func Concrete() {}
    88  //
    89  //	func foo(fn func()) {
    90  //		fn()
    91  //	}
    92  //
    93  // to:
    94  //
    95  //	func foo(fn func()) {
    96  //		if internal/abi.FuncPCABIInternal(fn) == internal/abi.FuncPCABIInternal(Concrete) {
    97  //			Concrete()
    98  //		} else {
    99  //			fn()
   100  //		}
   101  //	}
   102  //
   103  // The primary benefit of this transformation is enabling inlining of the
   104  // direct call.
   105  func ProfileGuided(fn *ir.Func, p *pgoir.Profile) {
   106  	ir.CurFunc = fn
   107  
   108  	name := ir.LinkFuncName(fn)
   109  
   110  	var jsonW *json.Encoder
   111  	if base.Debug.PGODebug >= 3 {
   112  		jsonW = json.NewEncoder(os.Stdout)
   113  	}
   114  
   115  	var edit func(n ir.Node) ir.Node
   116  	edit = func(n ir.Node) ir.Node {
   117  		if n == nil {
   118  			return n
   119  		}
   120  
   121  		ir.EditChildren(n, edit)
   122  
   123  		call, ok := n.(*ir.CallExpr)
   124  		if !ok {
   125  			return n
   126  		}
   127  
   128  		var stat *CallStat
   129  		if base.Debug.PGODebug >= 3 {
   130  			// Statistics about every single call. Handy for external data analysis.
   131  			//
   132  			// TODO(prattmic): Log via logopt?
   133  			stat = constructCallStat(p, fn, name, call)
   134  			if stat != nil {
   135  				defer func() {
   136  					jsonW.Encode(&stat)
   137  				}()
   138  			}
   139  		}
   140  
   141  		op := call.Op()
   142  		if op != ir.OCALLFUNC && op != ir.OCALLINTER {
   143  			return n
   144  		}
   145  
   146  		if base.Debug.PGODebug >= 2 {
   147  			fmt.Printf("%v: PGO devirtualize considering call %v\n", ir.Line(call), call)
   148  		}
   149  
   150  		if call.GoDefer {
   151  			if base.Debug.PGODebug >= 2 {
   152  				fmt.Printf("%v: can't PGO devirtualize go/defer call %v\n", ir.Line(call), call)
   153  			}
   154  			return n
   155  		}
   156  
   157  		var newNode ir.Node
   158  		var callee *ir.Func
   159  		var weight int64
   160  		switch op {
   161  		case ir.OCALLFUNC:
   162  			newNode, callee, weight = maybeDevirtualizeFunctionCall(p, fn, call)
   163  		case ir.OCALLINTER:
   164  			newNode, callee, weight = maybeDevirtualizeInterfaceCall(p, fn, call)
   165  		default:
   166  			panic("unreachable")
   167  		}
   168  
   169  		if newNode == nil {
   170  			return n
   171  		}
   172  
   173  		if stat != nil {
   174  			stat.Devirtualized = ir.LinkFuncName(callee)
   175  			stat.DevirtualizedWeight = weight
   176  		}
   177  
   178  		return newNode
   179  	}
   180  
   181  	ir.EditChildren(fn, edit)
   182  }
   183  
   184  // Devirtualize interface call if possible and eligible. Returns the new
   185  // ir.Node if call was devirtualized, and if so also the callee and weight of
   186  // the devirtualized edge.
   187  func maybeDevirtualizeInterfaceCall(p *pgoir.Profile, fn *ir.Func, call *ir.CallExpr) (ir.Node, *ir.Func, int64) {
   188  	if base.Debug.PGODevirtualize < 1 {
   189  		return nil, nil, 0
   190  	}
   191  
   192  	// Bail if we do not have a hot callee.
   193  	callee, weight := findHotConcreteInterfaceCallee(p, fn, call)
   194  	if callee == nil {
   195  		return nil, nil, 0
   196  	}
   197  	// Bail if we do not have a Type node for the hot callee.
   198  	ctyp := methodRecvType(callee)
   199  	if ctyp == nil {
   200  		return nil, nil, 0
   201  	}
   202  	// Bail if we know for sure it won't inline.
   203  	if !shouldPGODevirt(callee) {
   204  		return nil, nil, 0
   205  	}
   206  	// Bail if de-selected by PGO Hash.
   207  	if !base.PGOHash.MatchPosWithInfo(call.Pos(), "devirt", nil) {
   208  		return nil, nil, 0
   209  	}
   210  
   211  	return rewriteInterfaceCall(call, fn, callee, ctyp), callee, weight
   212  }
   213  
   214  // Devirtualize an indirect function call if possible and eligible. Returns the new
   215  // ir.Node if call was devirtualized, and if so also the callee and weight of
   216  // the devirtualized edge.
   217  func maybeDevirtualizeFunctionCall(p *pgoir.Profile, fn *ir.Func, call *ir.CallExpr) (ir.Node, *ir.Func, int64) {
   218  	if base.Debug.PGODevirtualize < 2 {
   219  		return nil, nil, 0
   220  	}
   221  
   222  	// Bail if this is a direct call; no devirtualization necessary.
   223  	callee := pgoir.DirectCallee(call.Fun)
   224  	if callee != nil {
   225  		return nil, nil, 0
   226  	}
   227  
   228  	// Bail if we do not have a hot callee.
   229  	callee, weight := findHotConcreteFunctionCallee(p, fn, call)
   230  	if callee == nil {
   231  		return nil, nil, 0
   232  	}
   233  
   234  	// TODO(go.dev/issue/61577): Closures need the closure context passed
   235  	// via the context register. That requires extra plumbing that we
   236  	// haven't done yet.
   237  	if callee.OClosure != nil {
   238  		if base.Debug.PGODebug >= 3 {
   239  			fmt.Printf("callee %s is a closure, skipping\n", ir.FuncName(callee))
   240  		}
   241  		return nil, nil, 0
   242  	}
   243  	// runtime.memhash_varlen does not look like a closure, but it uses
   244  	// internal/runtime/sys.GetClosurePtr to access data encoded by
   245  	// callers, which are generated by
   246  	// cmd/compile/internal/reflectdata.genhash.
   247  	if callee.Sym().Pkg.Path == "runtime" && callee.Sym().Name == "memhash_varlen" {
   248  		if base.Debug.PGODebug >= 3 {
   249  			fmt.Printf("callee %s is a closure (runtime.memhash_varlen), skipping\n", ir.FuncName(callee))
   250  		}
   251  		return nil, nil, 0
   252  	}
   253  	// TODO(prattmic): We don't properly handle methods as callees in two
   254  	// different dimensions:
   255  	//
   256  	// 1. Method expressions. e.g.,
   257  	//
   258  	//      var fn func(*os.File, []byte) (int, error) = (*os.File).Read
   259  	//
   260  	// In this case, typ will report *os.File as the receiver while
   261  	// ctyp reports it as the first argument. types.Identical ignores
   262  	// receiver parameters, so it treats these as different, even though
   263  	// they are still call compatible.
   264  	//
   265  	// 2. Method values. e.g.,
   266  	//
   267  	//      var f *os.File
   268  	//      var fn func([]byte) (int, error) = f.Read
   269  	//
   270  	// types.Identical will treat these as compatible (since receiver
   271  	// parameters are ignored). However, in this case, we do not call
   272  	// (*os.File).Read directly. Instead, f is stored in closure context
   273  	// and we call the wrapper (*os.File).Read-fm. However, runtime/pprof
   274  	// hides wrappers from profiles, making it appear that there is a call
   275  	// directly to the method. We could recognize this pattern return the
   276  	// wrapper rather than the method.
   277  	//
   278  	// N.B. perf profiles will report wrapper symbols directly, so
   279  	// ideally we should support direct wrapper references as well.
   280  	if callee.Type().Recv() != nil {
   281  		if base.Debug.PGODebug >= 3 {
   282  			fmt.Printf("callee %s is a method, skipping\n", ir.FuncName(callee))
   283  		}
   284  		return nil, nil, 0
   285  	}
   286  
   287  	// Bail if we know for sure it won't inline.
   288  	if !shouldPGODevirt(callee) {
   289  		return nil, nil, 0
   290  	}
   291  	// Bail if de-selected by PGO Hash.
   292  	if !base.PGOHash.MatchPosWithInfo(call.Pos(), "devirt", nil) {
   293  		return nil, nil, 0
   294  	}
   295  
   296  	return rewriteFunctionCall(call, fn, callee), callee, weight
   297  }
   298  
   299  // shouldPGODevirt checks if we should perform PGO devirtualization to the
   300  // target function.
   301  //
   302  // PGO devirtualization is most valuable when the callee is inlined, so if it
   303  // won't inline we can skip devirtualizing.
   304  func shouldPGODevirt(fn *ir.Func) bool {
   305  	var reason string
   306  	if base.Flag.LowerM > 1 || logopt.Enabled() {
   307  		defer func() {
   308  			if reason != "" {
   309  				if base.Flag.LowerM > 1 {
   310  					fmt.Printf("%v: should not PGO devirtualize %v: %s\n", ir.Line(fn), ir.FuncName(fn), reason)
   311  				}
   312  				if logopt.Enabled() {
   313  					logopt.LogOpt(fn.Pos(), ": should not PGO devirtualize function", "pgoir-devirtualize", ir.FuncName(fn), reason)
   314  				}
   315  			}
   316  		}()
   317  	}
   318  
   319  	reason = inline.InlineImpossible(fn)
   320  	if reason != "" {
   321  		return false
   322  	}
   323  
   324  	// TODO(prattmic): checking only InlineImpossible is very conservative,
   325  	// primarily excluding only functions with pragmas. We probably want to
   326  	// move in either direction. Either:
   327  	//
   328  	// 1. Don't even bother to check InlineImpossible, as it affects so few
   329  	// functions.
   330  	//
   331  	// 2. Or consider the function body (notably cost) to better determine
   332  	// if the function will actually inline.
   333  
   334  	return true
   335  }
   336  
   337  // constructCallStat builds an initial CallStat describing this call, for
   338  // logging. If the call is devirtualized, the devirtualization fields should be
   339  // updated.
   340  func constructCallStat(p *pgoir.Profile, fn *ir.Func, name string, call *ir.CallExpr) *CallStat {
   341  	switch call.Op() {
   342  	case ir.OCALLFUNC, ir.OCALLINTER, ir.OCALLMETH:
   343  	default:
   344  		// We don't care about logging builtin functions.
   345  		return nil
   346  	}
   347  
   348  	stat := CallStat{
   349  		Pkg:    base.Ctxt.Pkgpath,
   350  		Pos:    ir.Line(call),
   351  		Caller: name,
   352  	}
   353  
   354  	offset := pgoir.NodeLineOffset(call, fn)
   355  
   356  	hotter := func(e *pgoir.IREdge) bool {
   357  		if stat.Hottest == "" {
   358  			return true
   359  		}
   360  		if e.Weight != stat.HottestWeight {
   361  			return e.Weight > stat.HottestWeight
   362  		}
   363  		// If weight is the same, arbitrarily sort lexicographally, as
   364  		// findHotConcreteCallee does.
   365  		return e.Dst.Name() < stat.Hottest
   366  	}
   367  
   368  	callerNode := p.WeightedCG.IRNodes[name]
   369  	if callerNode == nil {
   370  		return nil
   371  	}
   372  
   373  	// Sum of all edges from this callsite, regardless of callee.
   374  	// For direct calls, this should be the same as the single edge
   375  	// weight (except for multiple calls on one line, which we
   376  	// can't distinguish).
   377  	for _, edge := range callerNode.OutEdges {
   378  		if edge.CallSiteOffset != offset {
   379  			continue
   380  		}
   381  		stat.Weight += edge.Weight
   382  		if hotter(edge) {
   383  			stat.HottestWeight = edge.Weight
   384  			stat.Hottest = edge.Dst.Name()
   385  		}
   386  	}
   387  
   388  	switch call.Op() {
   389  	case ir.OCALLFUNC:
   390  		stat.Interface = false
   391  
   392  		callee := pgoir.DirectCallee(call.Fun)
   393  		if callee != nil {
   394  			stat.Direct = true
   395  			if stat.Hottest == "" {
   396  				stat.Hottest = ir.LinkFuncName(callee)
   397  			}
   398  		} else {
   399  			stat.Direct = false
   400  		}
   401  	case ir.OCALLINTER:
   402  		stat.Direct = false
   403  		stat.Interface = true
   404  	case ir.OCALLMETH:
   405  		base.FatalfAt(call.Pos(), "OCALLMETH missed by typecheck")
   406  	}
   407  
   408  	return &stat
   409  }
   410  
   411  // copyInputs copies the inputs to a call: the receiver (for interface calls)
   412  // or function value (for function value calls) and the arguments. These
   413  // expressions are evaluated once and assigned to temporaries.
   414  //
   415  // The assignment statement is added to init and the copied receiver/fn
   416  // expression and copied arguments expressions are returned.
   417  func copyInputs(curfn *ir.Func, pos src.XPos, recvOrFn ir.Node, args []ir.Node, init *ir.Nodes) (ir.Node, []ir.Node) {
   418  	// Evaluate receiver/fn and argument expressions. The receiver/fn is
   419  	// used twice but we don't want to cause side effects twice. The
   420  	// arguments are used in two different calls and we can't trivially
   421  	// copy them.
   422  	//
   423  	// recvOrFn must be first in the assignment list as its side effects
   424  	// must be ordered before argument side effects.
   425  	var lhs, rhs []ir.Node
   426  	newRecvOrFn := typecheck.TempAt(pos, curfn, recvOrFn.Type())
   427  	lhs = append(lhs, newRecvOrFn)
   428  	rhs = append(rhs, recvOrFn)
   429  
   430  	for _, arg := range args {
   431  		argvar := typecheck.TempAt(pos, curfn, arg.Type())
   432  
   433  		lhs = append(lhs, argvar)
   434  		rhs = append(rhs, arg)
   435  	}
   436  
   437  	asList := ir.NewAssignListStmt(pos, ir.OAS2, lhs, rhs)
   438  	init.Append(typecheck.Stmt(asList))
   439  
   440  	return newRecvOrFn, lhs[1:]
   441  }
   442  
   443  // retTemps returns a slice of temporaries to be used for storing result values from call.
   444  func retTemps(curfn *ir.Func, pos src.XPos, call *ir.CallExpr) []ir.Node {
   445  	sig := call.Fun.Type()
   446  	var retvars []ir.Node
   447  	for _, ret := range sig.Results() {
   448  		retvars = append(retvars, typecheck.TempAt(pos, curfn, ret.Type))
   449  	}
   450  	return retvars
   451  }
   452  
   453  // condCall returns an ir.InlinedCallExpr that performs a call to thenCall if
   454  // cond is true and elseCall if cond is false. The return variables of the
   455  // InlinedCallExpr evaluate to the return values from the call.
   456  func condCall(curfn *ir.Func, pos src.XPos, cond ir.Node, thenCall, elseCall *ir.CallExpr, init ir.Nodes) *ir.InlinedCallExpr {
   457  	// Doesn't matter whether we use thenCall or elseCall, they must have
   458  	// the same return types.
   459  	retvars := retTemps(curfn, pos, thenCall)
   460  
   461  	var thenBlock, elseBlock ir.Nodes
   462  	if len(retvars) == 0 {
   463  		thenBlock.Append(thenCall)
   464  		elseBlock.Append(elseCall)
   465  	} else {
   466  		// Copy slice so edits in one location don't affect another.
   467  		thenRet := append([]ir.Node(nil), retvars...)
   468  		thenAsList := ir.NewAssignListStmt(pos, ir.OAS2, thenRet, []ir.Node{thenCall})
   469  		thenBlock.Append(typecheck.Stmt(thenAsList))
   470  
   471  		elseRet := append([]ir.Node(nil), retvars...)
   472  		elseAsList := ir.NewAssignListStmt(pos, ir.OAS2, elseRet, []ir.Node{elseCall})
   473  		elseBlock.Append(typecheck.Stmt(elseAsList))
   474  	}
   475  
   476  	nif := ir.NewIfStmt(pos, cond, thenBlock, elseBlock)
   477  	nif.SetInit(init)
   478  	nif.Likely = true
   479  
   480  	body := []ir.Node{typecheck.Stmt(nif)}
   481  
   482  	// This isn't really an inlined call of course, but InlinedCallExpr
   483  	// makes handling reassignment of return values easier.
   484  	res := ir.NewInlinedCallExpr(pos, body, retvars)
   485  	res.SetType(thenCall.Type())
   486  	res.SetTypecheck(1)
   487  	res.Reshape = thenCall.Reshape
   488  	return res
   489  }
   490  
   491  // rewriteInterfaceCall devirtualizes the given interface call using a direct
   492  // method call to concretetyp.
   493  func rewriteInterfaceCall(call *ir.CallExpr, curfn, callee *ir.Func, concretetyp *types.Type) ir.Node {
   494  	if base.Flag.LowerM != 0 {
   495  		fmt.Printf("%v: PGO devirtualizing interface call %v to %v\n", ir.Line(call), call.Fun, callee)
   496  	}
   497  
   498  	// We generate an OINCALL of:
   499  	//
   500  	// var recv Iface
   501  	//
   502  	// var arg1 A1
   503  	// var argN AN
   504  	//
   505  	// var ret1 R1
   506  	// var retN RN
   507  	//
   508  	// recv, arg1, argN = recv expr, arg1 expr, argN expr
   509  	//
   510  	// t, ok := recv.(Concrete)
   511  	// if ok {
   512  	//   ret1, retN = t.Method(arg1, ... argN)
   513  	// } else {
   514  	//   ret1, retN = recv.Method(arg1, ... argN)
   515  	// }
   516  	//
   517  	// OINCALL retvars: ret1, ... retN
   518  	//
   519  	// This isn't really an inlined call of course, but InlinedCallExpr
   520  	// makes handling reassignment of return values easier.
   521  	//
   522  	// TODO(prattmic): This increases the size of the AST in the caller,
   523  	// making it less like to inline. We may want to compensate for this
   524  	// somehow.
   525  
   526  	sel := call.Fun.(*ir.SelectorExpr)
   527  	method := sel.Sel
   528  	pos := call.Pos()
   529  	init := ir.TakeInit(call)
   530  
   531  	recv, args := copyInputs(curfn, pos, sel.X, call.Args.Take(), &init)
   532  
   533  	// Copy slice so edits in one location don't affect another.
   534  	argvars := append([]ir.Node(nil), args...)
   535  	call.Args = argvars
   536  
   537  	tmpnode := typecheck.TempAt(base.Pos, curfn, concretetyp)
   538  	tmpok := typecheck.TempAt(base.Pos, curfn, types.Types[types.TBOOL])
   539  
   540  	assert := ir.NewTypeAssertExpr(pos, recv, concretetyp)
   541  
   542  	assertAsList := ir.NewAssignListStmt(pos, ir.OAS2, []ir.Node{tmpnode, tmpok}, []ir.Node{typecheck.Expr(assert)})
   543  	init.Append(typecheck.Stmt(assertAsList))
   544  
   545  	concreteCallee := typecheck.XDotMethod(pos, tmpnode, method, true)
   546  	// Copy slice so edits in one location don't affect another.
   547  	argvars = append([]ir.Node(nil), argvars...)
   548  	concreteCall := typecheck.Call(pos, concreteCallee, argvars, call.IsDDD).(*ir.CallExpr)
   549  
   550  	res := condCall(curfn, pos, tmpok, concreteCall, call, init)
   551  
   552  	if base.Debug.PGODebug >= 3 {
   553  		fmt.Printf("PGO devirtualizing interface call to %+v. After: %+v\n", concretetyp, res)
   554  	}
   555  
   556  	return res
   557  }
   558  
   559  // rewriteFunctionCall devirtualizes the given OCALLFUNC using a direct
   560  // function call to callee.
   561  func rewriteFunctionCall(call *ir.CallExpr, curfn, callee *ir.Func) ir.Node {
   562  	if base.Flag.LowerM != 0 {
   563  		fmt.Printf("%v: PGO devirtualizing function call %v to %v\n", ir.Line(call), call.Fun, callee)
   564  	}
   565  
   566  	// We generate an OINCALL of:
   567  	//
   568  	// var fn FuncType
   569  	//
   570  	// var arg1 A1
   571  	// var argN AN
   572  	//
   573  	// var ret1 R1
   574  	// var retN RN
   575  	//
   576  	// fn, arg1, argN = fn expr, arg1 expr, argN expr
   577  	//
   578  	// fnPC := internal/abi.FuncPCABIInternal(fn)
   579  	// concretePC := internal/abi.FuncPCABIInternal(concrete)
   580  	//
   581  	// if fnPC == concretePC {
   582  	//   ret1, retN = concrete(arg1, ... argN) // Same closure context passed (TODO)
   583  	// } else {
   584  	//   ret1, retN = fn(arg1, ... argN)
   585  	// }
   586  	//
   587  	// OINCALL retvars: ret1, ... retN
   588  	//
   589  	// This isn't really an inlined call of course, but InlinedCallExpr
   590  	// makes handling reassignment of return values easier.
   591  
   592  	pos := call.Pos()
   593  	init := ir.TakeInit(call)
   594  
   595  	fn, args := copyInputs(curfn, pos, call.Fun, call.Args.Take(), &init)
   596  
   597  	// Copy slice so edits in one location don't affect another.
   598  	argvars := append([]ir.Node(nil), args...)
   599  	call.Args = argvars
   600  
   601  	// FuncPCABIInternal takes an interface{}, emulate that. This is needed
   602  	// for to ensure we get the MAKEFACE we need for SSA.
   603  	fnIface := typecheck.Expr(ir.NewConvExpr(pos, ir.OCONV, types.Types[types.TINTER], fn))
   604  	calleeIface := typecheck.Expr(ir.NewConvExpr(pos, ir.OCONV, types.Types[types.TINTER], callee.Nname))
   605  
   606  	fnPC := ir.FuncPC(pos, fnIface, obj.ABIInternal)
   607  	concretePC := ir.FuncPC(pos, calleeIface, obj.ABIInternal)
   608  
   609  	pcEq := typecheck.Expr(ir.NewBinaryExpr(base.Pos, ir.OEQ, fnPC, concretePC))
   610  
   611  	// TODO(go.dev/issue/61577): Handle callees that a closures and need a
   612  	// copy of the closure context from call. For now, we skip callees that
   613  	// are closures in maybeDevirtualizeFunctionCall.
   614  	if callee.OClosure != nil {
   615  		base.Fatalf("Callee is a closure: %+v", callee)
   616  	}
   617  
   618  	// Copy slice so edits in one location don't affect another.
   619  	argvars = append([]ir.Node(nil), argvars...)
   620  	concreteCall := typecheck.Call(pos, callee.Nname, argvars, call.IsDDD).(*ir.CallExpr)
   621  
   622  	res := condCall(curfn, pos, pcEq, concreteCall, call, init)
   623  
   624  	if base.Debug.PGODebug >= 3 {
   625  		fmt.Printf("PGO devirtualizing function call to %+v. After: %+v\n", ir.FuncName(callee), res)
   626  	}
   627  
   628  	return res
   629  }
   630  
   631  // methodRecvType returns the type containing method fn. Returns nil if fn
   632  // is not a method.
   633  func methodRecvType(fn *ir.Func) *types.Type {
   634  	recv := fn.Nname.Type().Recv()
   635  	if recv == nil {
   636  		return nil
   637  	}
   638  	return recv.Type
   639  }
   640  
   641  // interfaceCallRecvTypeAndMethod returns the type and the method of the interface
   642  // used in an interface call.
   643  func interfaceCallRecvTypeAndMethod(call *ir.CallExpr) (*types.Type, *types.Sym) {
   644  	if call.Op() != ir.OCALLINTER {
   645  		base.Fatalf("Call isn't OCALLINTER: %+v", call)
   646  	}
   647  
   648  	sel, ok := call.Fun.(*ir.SelectorExpr)
   649  	if !ok {
   650  		base.Fatalf("OCALLINTER doesn't contain SelectorExpr: %+v", call)
   651  	}
   652  
   653  	return sel.X.Type(), sel.Sel
   654  }
   655  
   656  // findHotConcreteCallee returns the *ir.Func of the hottest callee of a call,
   657  // if available, and its edge weight. extraFn can perform additional
   658  // applicability checks on each candidate edge. If extraFn returns false,
   659  // candidate will not be considered a valid callee candidate.
   660  func findHotConcreteCallee(p *pgoir.Profile, caller *ir.Func, call *ir.CallExpr, extraFn func(callerName string, callOffset int, candidate *pgoir.IREdge) bool) (*ir.Func, int64) {
   661  	callerName := ir.LinkFuncName(caller)
   662  	callerNode := p.WeightedCG.IRNodes[callerName]
   663  	callOffset := pgoir.NodeLineOffset(call, caller)
   664  
   665  	if callerNode == nil {
   666  		return nil, 0
   667  	}
   668  
   669  	var hottest *pgoir.IREdge
   670  
   671  	// Returns true if e is hotter than hottest.
   672  	//
   673  	// Naively this is just e.Weight > hottest.Weight, but because OutEdges
   674  	// has arbitrary iteration order, we need to apply additional sort
   675  	// criteria when e.Weight == hottest.Weight to ensure we have stable
   676  	// selection.
   677  	hotter := func(e *pgoir.IREdge) bool {
   678  		if hottest == nil {
   679  			return true
   680  		}
   681  		if e.Weight != hottest.Weight {
   682  			return e.Weight > hottest.Weight
   683  		}
   684  
   685  		// Now e.Weight == hottest.Weight, we must select on other
   686  		// criteria.
   687  
   688  		// If only one edge has IR, prefer that one.
   689  		if (hottest.Dst.AST == nil) != (e.Dst.AST == nil) {
   690  			if e.Dst.AST != nil {
   691  				return true
   692  			}
   693  			return false
   694  		}
   695  
   696  		// Arbitrary, but the callee names will always differ. Select
   697  		// the lexicographically first callee.
   698  		return e.Dst.Name() < hottest.Dst.Name()
   699  	}
   700  
   701  	for _, e := range callerNode.OutEdges {
   702  		if e.CallSiteOffset != callOffset {
   703  			continue
   704  		}
   705  
   706  		if !hotter(e) {
   707  			// TODO(prattmic): consider total caller weight? i.e.,
   708  			// if the hottest callee is only 10% of the weight,
   709  			// maybe don't devirtualize? Similarly, if this is call
   710  			// is globally very cold, there is not much value in
   711  			// devirtualizing.
   712  			if base.Debug.PGODebug >= 2 {
   713  				fmt.Printf("%v: edge %s:%d -> %s (weight %d): too cold (hottest %d)\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight, hottest.Weight)
   714  			}
   715  			continue
   716  		}
   717  
   718  		if e.Dst.AST == nil {
   719  			// Destination isn't visible from this package
   720  			// compilation.
   721  			//
   722  			// We must assume it implements the interface.
   723  			//
   724  			// We still record this as the hottest callee so far
   725  			// because we only want to return the #1 hottest
   726  			// callee. If we skip this then we'd return the #2
   727  			// hottest callee.
   728  			if base.Debug.PGODebug >= 2 {
   729  				fmt.Printf("%v: edge %s:%d -> %s (weight %d) (missing IR): hottest so far\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight)
   730  			}
   731  			hottest = e
   732  			continue
   733  		}
   734  
   735  		if extraFn != nil && !extraFn(callerName, callOffset, e) {
   736  			continue
   737  		}
   738  
   739  		if base.Debug.PGODebug >= 2 {
   740  			fmt.Printf("%v: edge %s:%d -> %s (weight %d): hottest so far\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight)
   741  		}
   742  		hottest = e
   743  	}
   744  
   745  	if hottest == nil || hottest.Weight == 0 {
   746  		if base.Debug.PGODebug >= 2 {
   747  			fmt.Printf("%v: call %s:%d: no hot callee\n", ir.Line(call), callerName, callOffset)
   748  		}
   749  		return nil, 0
   750  	}
   751  
   752  	if base.Debug.PGODebug >= 2 {
   753  		fmt.Printf("%v: call %s:%d: hottest callee %s (weight %d)\n", ir.Line(call), callerName, callOffset, hottest.Dst.Name(), hottest.Weight)
   754  	}
   755  	return hottest.Dst.AST, hottest.Weight
   756  }
   757  
   758  // findHotConcreteInterfaceCallee returns the *ir.Func of the hottest callee of an
   759  // interface call, if available, and its edge weight.
   760  func findHotConcreteInterfaceCallee(p *pgoir.Profile, caller *ir.Func, call *ir.CallExpr) (*ir.Func, int64) {
   761  	inter, method := interfaceCallRecvTypeAndMethod(call)
   762  
   763  	return findHotConcreteCallee(p, caller, call, func(callerName string, callOffset int, e *pgoir.IREdge) bool {
   764  		ctyp := methodRecvType(e.Dst.AST)
   765  		if ctyp == nil {
   766  			// Not a method.
   767  			// TODO(prattmic): Support non-interface indirect calls.
   768  			if base.Debug.PGODebug >= 2 {
   769  				fmt.Printf("%v: edge %s:%d -> %s (weight %d): callee not a method\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight)
   770  			}
   771  			return false
   772  		}
   773  
   774  		// If ctyp doesn't implement inter it is most likely from a
   775  		// different call on the same line
   776  		if !typecheck.Implements(ctyp, inter) {
   777  			// TODO(prattmic): this is overly strict. Consider if
   778  			// ctyp is a partial implementation of an interface
   779  			// that gets embedded in types that complete the
   780  			// interface. It would still be OK to devirtualize a
   781  			// call to this method.
   782  			//
   783  			// What we'd need to do is check that the function
   784  			// pointer in the itab matches the method we want,
   785  			// rather than doing a full type assertion.
   786  			if base.Debug.PGODebug >= 2 {
   787  				why := typecheck.ImplementsExplain(ctyp, inter)
   788  				fmt.Printf("%v: edge %s:%d -> %s (weight %d): %v doesn't implement %v (%s)\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight, ctyp, inter, why)
   789  			}
   790  			return false
   791  		}
   792  
   793  		// If the method name is different it is most likely from a
   794  		// different call on the same line
   795  		if !strings.HasSuffix(e.Dst.Name(), "."+method.Name) {
   796  			if base.Debug.PGODebug >= 2 {
   797  				fmt.Printf("%v: edge %s:%d -> %s (weight %d): callee is a different method\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight)
   798  			}
   799  			return false
   800  		}
   801  
   802  		return true
   803  	})
   804  }
   805  
   806  // findHotConcreteFunctionCallee returns the *ir.Func of the hottest callee of an
   807  // indirect function call, if available, and its edge weight.
   808  func findHotConcreteFunctionCallee(p *pgoir.Profile, caller *ir.Func, call *ir.CallExpr) (*ir.Func, int64) {
   809  	typ := call.Fun.Type().Underlying()
   810  
   811  	return findHotConcreteCallee(p, caller, call, func(callerName string, callOffset int, e *pgoir.IREdge) bool {
   812  		ctyp := e.Dst.AST.Type().Underlying()
   813  
   814  		// If ctyp doesn't match typ it is most likely from a different
   815  		// call on the same line.
   816  		//
   817  		// Note that we are comparing underlying types, as different
   818  		// defined types are OK. e.g., a call to a value of type
   819  		// net/http.HandlerFunc can be devirtualized to a function with
   820  		// the same underlying type.
   821  		if !types.Identical(typ, ctyp) {
   822  			if base.Debug.PGODebug >= 2 {
   823  				fmt.Printf("%v: edge %s:%d -> %s (weight %d): %v doesn't match %v\n", ir.Line(call), callerName, callOffset, e.Dst.Name(), e.Weight, ctyp, typ)
   824  			}
   825  			return false
   826  		}
   827  
   828  		return true
   829  	})
   830  }
   831
View as plain text