Source file src/pkg/cmd/compile/internal/gc/inl.go

     1	// Copyright 2011 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	// The inlining facility makes 2 passes: first caninl determines which
     6	// functions are suitable for inlining, and for those that are it
     7	// saves a copy of the body. Then inlcalls walks each function body to
     8	// expand calls to inlinable functions.
     9	//
    10	// The debug['l'] flag controls the aggressiveness. Note that main() swaps level 0 and 1,
    11	// making 1 the default and -l disable. Additional levels (beyond -l) may be buggy and
    12	// are not supported.
    13	//      0: disabled
    14	//      1: 80-nodes leaf functions, oneliners, panic, lazy typechecking (default)
    15	//      2: (unassigned)
    16	//      3: (unassigned)
    17	//      4: allow non-leaf functions
    18	//
    19	// At some point this may get another default and become switch-offable with -N.
    20	//
    21	// The -d typcheckinl flag enables early typechecking of all imported bodies,
    22	// which is useful to flush out bugs.
    23	//
    24	// The debug['m'] flag enables diagnostic output.  a single -m is useful for verifying
    25	// which calls get inlined or not, more is for debugging, and may go away at any point.
    26	
    27	package gc
    28	
    29	import (
    30		"cmd/compile/internal/types"
    31		"cmd/internal/obj"
    32		"cmd/internal/src"
    33		"fmt"
    34		"strings"
    35	)
    36	
    37	// Inlining budget parameters, gathered in one place
    38	const (
    39		inlineMaxBudget       = 80
    40		inlineExtraAppendCost = 0
    41		// default is to inline if there's at most one call. -l=4 overrides this by using 1 instead.
    42		inlineExtraCallCost  = 57              // 57 was benchmarked to provided most benefit with no bad surprises; see https://github.com/golang/go/issues/19348#issuecomment-439370742
    43		inlineExtraPanicCost = 1               // do not penalize inlining panics.
    44		inlineExtraThrowCost = inlineMaxBudget // with current (2018-05/1.11) code, inlining runtime.throw does not help.
    45	
    46		inlineBigFunctionNodes   = 5000 // Functions with this many nodes are considered "big".
    47		inlineBigFunctionMaxCost = 20   // Max cost of inlinee when inlining into a "big" function.
    48	)
    49	
    50	// Get the function's package. For ordinary functions it's on the ->sym, but for imported methods
    51	// the ->sym can be re-used in the local package, so peel it off the receiver's type.
    52	func fnpkg(fn *Node) *types.Pkg {
    53		if fn.IsMethod() {
    54			// method
    55			rcvr := fn.Type.Recv().Type
    56	
    57			if rcvr.IsPtr() {
    58				rcvr = rcvr.Elem()
    59			}
    60			if rcvr.Sym == nil {
    61				Fatalf("receiver with no sym: [%v] %L  (%v)", fn.Sym, fn, rcvr)
    62			}
    63			return rcvr.Sym.Pkg
    64		}
    65	
    66		// non-method
    67		return fn.Sym.Pkg
    68	}
    69	
    70	// Lazy typechecking of imported bodies. For local functions, caninl will set ->typecheck
    71	// because they're a copy of an already checked body.
    72	func typecheckinl(fn *Node) {
    73		lno := setlineno(fn)
    74	
    75		expandInline(fn)
    76	
    77		// typecheckinl is only for imported functions;
    78		// their bodies may refer to unsafe as long as the package
    79		// was marked safe during import (which was checked then).
    80		// the ->inl of a local function has been typechecked before caninl copied it.
    81		pkg := fnpkg(fn)
    82	
    83		if pkg == localpkg || pkg == nil {
    84			return // typecheckinl on local function
    85		}
    86	
    87		if Debug['m'] > 2 || Debug_export != 0 {
    88			fmt.Printf("typecheck import [%v] %L { %#v }\n", fn.Sym, fn, asNodes(fn.Func.Inl.Body))
    89		}
    90	
    91		savefn := Curfn
    92		Curfn = fn
    93		typecheckslice(fn.Func.Inl.Body, ctxStmt)
    94		Curfn = savefn
    95	
    96		// During typechecking, declarations are added to
    97		// Curfn.Func.Dcl. Move them to Inl.Dcl for consistency with
    98		// how local functions behave. (Append because typecheckinl
    99		// may be called multiple times.)
   100		fn.Func.Inl.Dcl = append(fn.Func.Inl.Dcl, fn.Func.Dcl...)
   101		fn.Func.Dcl = nil
   102	
   103		lineno = lno
   104	}
   105	
   106	// Caninl determines whether fn is inlineable.
   107	// If so, caninl saves fn->nbody in fn->inl and substitutes it with a copy.
   108	// fn and ->nbody will already have been typechecked.
   109	func caninl(fn *Node) {
   110		if fn.Op != ODCLFUNC {
   111			Fatalf("caninl %v", fn)
   112		}
   113		if fn.Func.Nname == nil {
   114			Fatalf("caninl no nname %+v", fn)
   115		}
   116	
   117		var reason string // reason, if any, that the function was not inlined
   118		if Debug['m'] > 1 {
   119			defer func() {
   120				if reason != "" {
   121					fmt.Printf("%v: cannot inline %v: %s\n", fn.Line(), fn.Func.Nname, reason)
   122				}
   123			}()
   124		}
   125	
   126		// If marked "go:noinline", don't inline
   127		if fn.Func.Pragma&Noinline != 0 {
   128			reason = "marked go:noinline"
   129			return
   130		}
   131	
   132		// If marked "go:norace" and -race compilation, don't inline.
   133		if flag_race && fn.Func.Pragma&Norace != 0 {
   134			reason = "marked go:norace with -race compilation"
   135			return
   136		}
   137	
   138		// If marked "go:cgo_unsafe_args", don't inline, since the
   139		// function makes assumptions about its argument frame layout.
   140		if fn.Func.Pragma&CgoUnsafeArgs != 0 {
   141			reason = "marked go:cgo_unsafe_args"
   142			return
   143		}
   144	
   145		// If marked as "go:uintptrescapes", don't inline, since the
   146		// escape information is lost during inlining.
   147		if fn.Func.Pragma&UintptrEscapes != 0 {
   148			reason = "marked as having an escaping uintptr argument"
   149			return
   150		}
   151	
   152		// The nowritebarrierrec checker currently works at function
   153		// granularity, so inlining yeswritebarrierrec functions can
   154		// confuse it (#22342). As a workaround, disallow inlining
   155		// them for now.
   156		if fn.Func.Pragma&Yeswritebarrierrec != 0 {
   157			reason = "marked go:yeswritebarrierrec"
   158			return
   159		}
   160	
   161		// If fn has no body (is defined outside of Go), cannot inline it.
   162		if fn.Nbody.Len() == 0 {
   163			reason = "no function body"
   164			return
   165		}
   166	
   167		if fn.Typecheck() == 0 {
   168			Fatalf("caninl on non-typechecked function %v", fn)
   169		}
   170	
   171		n := fn.Func.Nname
   172		if n.Func.InlinabilityChecked() {
   173			return
   174		}
   175		defer n.Func.SetInlinabilityChecked(true)
   176	
   177		cc := int32(inlineExtraCallCost)
   178		if Debug['l'] == 4 {
   179			cc = 1 // this appears to yield better performance than 0.
   180		}
   181	
   182		// At this point in the game the function we're looking at may
   183		// have "stale" autos, vars that still appear in the Dcl list, but
   184		// which no longer have any uses in the function body (due to
   185		// elimination by deadcode). We'd like to exclude these dead vars
   186		// when creating the "Inline.Dcl" field below; to accomplish this,
   187		// the hairyVisitor below builds up a map of used/referenced
   188		// locals, and we use this map to produce a pruned Inline.Dcl
   189		// list. See issue 25249 for more context.
   190	
   191		visitor := hairyVisitor{
   192			budget:        inlineMaxBudget,
   193			extraCallCost: cc,
   194			usedLocals:    make(map[*Node]bool),
   195		}
   196		if visitor.visitList(fn.Nbody) {
   197			reason = visitor.reason
   198			return
   199		}
   200		if visitor.budget < 0 {
   201			reason = fmt.Sprintf("function too complex: cost %d exceeds budget %d", inlineMaxBudget-visitor.budget, inlineMaxBudget)
   202			return
   203		}
   204	
   205		n.Func.Inl = &Inline{
   206			Cost: inlineMaxBudget - visitor.budget,
   207			Dcl:  inlcopylist(pruneUnusedAutos(n.Name.Defn.Func.Dcl, &visitor)),
   208			Body: inlcopylist(fn.Nbody.Slice()),
   209		}
   210	
   211		// hack, TODO, check for better way to link method nodes back to the thing with the ->inl
   212		// this is so export can find the body of a method
   213		fn.Type.FuncType().Nname = asTypesNode(n)
   214	
   215		if Debug['m'] > 1 {
   216			fmt.Printf("%v: can inline %#v as: %#v { %#v }\n", fn.Line(), n, fn.Type, asNodes(n.Func.Inl.Body))
   217		} else if Debug['m'] != 0 {
   218			fmt.Printf("%v: can inline %v\n", fn.Line(), n)
   219		}
   220	}
   221	
   222	// inlFlood marks n's inline body for export and recursively ensures
   223	// all called functions are marked too.
   224	func inlFlood(n *Node) {
   225		if n == nil {
   226			return
   227		}
   228		if n.Op != ONAME || n.Class() != PFUNC {
   229			Fatalf("inlFlood: unexpected %v, %v, %v", n, n.Op, n.Class())
   230		}
   231		if n.Func == nil {
   232			Fatalf("inlFlood: missing Func on %v", n)
   233		}
   234		if n.Func.Inl == nil {
   235			return
   236		}
   237	
   238		if n.Func.ExportInline() {
   239			return
   240		}
   241		n.Func.SetExportInline(true)
   242	
   243		typecheckinl(n)
   244	
   245		inspectList(asNodes(n.Func.Inl.Body), func(n *Node) bool {
   246			switch n.Op {
   247			case ONAME:
   248				// Mark any referenced global variables or
   249				// functions for reexport. Skip methods,
   250				// because they're reexported alongside their
   251				// receiver type.
   252				if n.Class() == PEXTERN || n.Class() == PFUNC && !n.isMethodExpression() {
   253					exportsym(n)
   254				}
   255	
   256			case OCALLFUNC, OCALLMETH:
   257				// Recursively flood any functions called by
   258				// this one.
   259				inlFlood(asNode(n.Left.Type.Nname()))
   260			}
   261			return true
   262		})
   263	}
   264	
   265	// hairyVisitor visits a function body to determine its inlining
   266	// hairiness and whether or not it can be inlined.
   267	type hairyVisitor struct {
   268		budget        int32
   269		reason        string
   270		extraCallCost int32
   271		usedLocals    map[*Node]bool
   272	}
   273	
   274	// Look for anything we want to punt on.
   275	func (v *hairyVisitor) visitList(ll Nodes) bool {
   276		for _, n := range ll.Slice() {
   277			if v.visit(n) {
   278				return true
   279			}
   280		}
   281		return false
   282	}
   283	
   284	func (v *hairyVisitor) visit(n *Node) bool {
   285		if n == nil {
   286			return false
   287		}
   288	
   289		switch n.Op {
   290		// Call is okay if inlinable and we have the budget for the body.
   291		case OCALLFUNC:
   292			// Functions that call runtime.getcaller{pc,sp} can not be inlined
   293			// because getcaller{pc,sp} expect a pointer to the caller's first argument.
   294			//
   295			// runtime.throw is a "cheap call" like panic in normal code.
   296			if n.Left.Op == ONAME && n.Left.Class() == PFUNC && isRuntimePkg(n.Left.Sym.Pkg) {
   297				fn := n.Left.Sym.Name
   298				if fn == "getcallerpc" || fn == "getcallersp" {
   299					v.reason = "call to " + fn
   300					return true
   301				}
   302				if fn == "throw" {
   303					v.budget -= inlineExtraThrowCost
   304					break
   305				}
   306			}
   307	
   308			if isIntrinsicCall(n) {
   309				v.budget--
   310				break
   311			}
   312	
   313			if fn := n.Left.Func; fn != nil && fn.Inl != nil {
   314				v.budget -= fn.Inl.Cost
   315				break
   316			}
   317			if n.Left.isMethodExpression() {
   318				if d := asNode(n.Left.Sym.Def); d != nil && d.Func.Inl != nil {
   319					v.budget -= d.Func.Inl.Cost
   320					break
   321				}
   322			}
   323			// TODO(mdempsky): Budget for OCLOSURE calls if we
   324			// ever allow that. See #15561 and #23093.
   325	
   326			// Call cost for non-leaf inlining.
   327			v.budget -= v.extraCallCost
   328	
   329		// Call is okay if inlinable and we have the budget for the body.
   330		case OCALLMETH:
   331			t := n.Left.Type
   332			if t == nil {
   333				Fatalf("no function type for [%p] %+v\n", n.Left, n.Left)
   334			}
   335			if t.Nname() == nil {
   336				Fatalf("no function definition for [%p] %+v\n", t, t)
   337			}
   338			if isRuntimePkg(n.Left.Sym.Pkg) {
   339				fn := n.Left.Sym.Name
   340				if fn == "heapBits.nextArena" {
   341					// Special case: explicitly allow
   342					// mid-stack inlining of
   343					// runtime.heapBits.next even though
   344					// it calls slow-path
   345					// runtime.heapBits.nextArena.
   346					break
   347				}
   348			}
   349			if inlfn := asNode(t.FuncType().Nname).Func; inlfn.Inl != nil {
   350				v.budget -= inlfn.Inl.Cost
   351				break
   352			}
   353			// Call cost for non-leaf inlining.
   354			v.budget -= v.extraCallCost
   355	
   356		// Things that are too hairy, irrespective of the budget
   357		case OCALL, OCALLINTER:
   358			// Call cost for non-leaf inlining.
   359			v.budget -= v.extraCallCost
   360	
   361		case OPANIC:
   362			v.budget -= inlineExtraPanicCost
   363	
   364		case ORECOVER:
   365			// recover matches the argument frame pointer to find
   366			// the right panic value, so it needs an argument frame.
   367			v.reason = "call to recover"
   368			return true
   369	
   370		case OCLOSURE,
   371			OCALLPART,
   372			ORANGE,
   373			OFOR,
   374			OFORUNTIL,
   375			OSELECT,
   376			OTYPESW,
   377			OGO,
   378			ODEFER,
   379			ODCLTYPE, // can't print yet
   380			OBREAK,
   381			ORETJMP:
   382			v.reason = "unhandled op " + n.Op.String()
   383			return true
   384	
   385		case OAPPEND:
   386			v.budget -= inlineExtraAppendCost
   387	
   388		case ODCLCONST, OEMPTY, OFALL, OLABEL:
   389			// These nodes don't produce code; omit from inlining budget.
   390			return false
   391	
   392		case OIF:
   393			if Isconst(n.Left, CTBOOL) {
   394				// This if and the condition cost nothing.
   395				return v.visitList(n.Ninit) || v.visitList(n.Nbody) ||
   396					v.visitList(n.Rlist)
   397			}
   398	
   399		case ONAME:
   400			if n.Class() == PAUTO {
   401				v.usedLocals[n] = true
   402			}
   403	
   404		}
   405	
   406		v.budget--
   407	
   408		// When debugging, don't stop early, to get full cost of inlining this function
   409		if v.budget < 0 && Debug['m'] < 2 {
   410			return true
   411		}
   412	
   413		return v.visit(n.Left) || v.visit(n.Right) ||
   414			v.visitList(n.List) || v.visitList(n.Rlist) ||
   415			v.visitList(n.Ninit) || v.visitList(n.Nbody)
   416	}
   417	
   418	// Inlcopy and inlcopylist recursively copy the body of a function.
   419	// Any name-like node of non-local class is marked for re-export by adding it to
   420	// the exportlist.
   421	func inlcopylist(ll []*Node) []*Node {
   422		s := make([]*Node, 0, len(ll))
   423		for _, n := range ll {
   424			s = append(s, inlcopy(n))
   425		}
   426		return s
   427	}
   428	
   429	func inlcopy(n *Node) *Node {
   430		if n == nil {
   431			return nil
   432		}
   433	
   434		switch n.Op {
   435		case ONAME, OTYPE, OLITERAL:
   436			return n
   437		}
   438	
   439		m := n.copy()
   440		if m.Func != nil {
   441			Fatalf("unexpected Func: %v", m)
   442		}
   443		m.Left = inlcopy(n.Left)
   444		m.Right = inlcopy(n.Right)
   445		m.List.Set(inlcopylist(n.List.Slice()))
   446		m.Rlist.Set(inlcopylist(n.Rlist.Slice()))
   447		m.Ninit.Set(inlcopylist(n.Ninit.Slice()))
   448		m.Nbody.Set(inlcopylist(n.Nbody.Slice()))
   449	
   450		return m
   451	}
   452	
   453	func countNodes(n *Node) int {
   454		if n == nil {
   455			return 0
   456		}
   457		cnt := 1
   458		cnt += countNodes(n.Left)
   459		cnt += countNodes(n.Right)
   460		for _, n1 := range n.Ninit.Slice() {
   461			cnt += countNodes(n1)
   462		}
   463		for _, n1 := range n.Nbody.Slice() {
   464			cnt += countNodes(n1)
   465		}
   466		for _, n1 := range n.List.Slice() {
   467			cnt += countNodes(n1)
   468		}
   469		for _, n1 := range n.Rlist.Slice() {
   470			cnt += countNodes(n1)
   471		}
   472		return cnt
   473	}
   474	
   475	// Inlcalls/nodelist/node walks fn's statements and expressions and substitutes any
   476	// calls made to inlineable functions. This is the external entry point.
   477	func inlcalls(fn *Node) {
   478		savefn := Curfn
   479		Curfn = fn
   480		maxCost := int32(inlineMaxBudget)
   481		if countNodes(fn) >= inlineBigFunctionNodes {
   482			maxCost = inlineBigFunctionMaxCost
   483		}
   484		fn = inlnode(fn, maxCost)
   485		if fn != Curfn {
   486			Fatalf("inlnode replaced curfn")
   487		}
   488		Curfn = savefn
   489	}
   490	
   491	// Turn an OINLCALL into a statement.
   492	func inlconv2stmt(n *Node) {
   493		n.Op = OBLOCK
   494	
   495		// n->ninit stays
   496		n.List.Set(n.Nbody.Slice())
   497	
   498		n.Nbody.Set(nil)
   499		n.Rlist.Set(nil)
   500	}
   501	
   502	// Turn an OINLCALL into a single valued expression.
   503	// The result of inlconv2expr MUST be assigned back to n, e.g.
   504	// 	n.Left = inlconv2expr(n.Left)
   505	func inlconv2expr(n *Node) *Node {
   506		r := n.Rlist.First()
   507		return addinit(r, append(n.Ninit.Slice(), n.Nbody.Slice()...))
   508	}
   509	
   510	// Turn the rlist (with the return values) of the OINLCALL in
   511	// n into an expression list lumping the ninit and body
   512	// containing the inlined statements on the first list element so
   513	// order will be preserved Used in return, oas2func and call
   514	// statements.
   515	func inlconv2list(n *Node) []*Node {
   516		if n.Op != OINLCALL || n.Rlist.Len() == 0 {
   517			Fatalf("inlconv2list %+v\n", n)
   518		}
   519	
   520		s := n.Rlist.Slice()
   521		s[0] = addinit(s[0], append(n.Ninit.Slice(), n.Nbody.Slice()...))
   522		return s
   523	}
   524	
   525	func inlnodelist(l Nodes, maxCost int32) {
   526		s := l.Slice()
   527		for i := range s {
   528			s[i] = inlnode(s[i], maxCost)
   529		}
   530	}
   531	
   532	// inlnode recurses over the tree to find inlineable calls, which will
   533	// be turned into OINLCALLs by mkinlcall. When the recursion comes
   534	// back up will examine left, right, list, rlist, ninit, ntest, nincr,
   535	// nbody and nelse and use one of the 4 inlconv/glue functions above
   536	// to turn the OINLCALL into an expression, a statement, or patch it
   537	// in to this nodes list or rlist as appropriate.
   538	// NOTE it makes no sense to pass the glue functions down the
   539	// recursion to the level where the OINLCALL gets created because they
   540	// have to edit /this/ n, so you'd have to push that one down as well,
   541	// but then you may as well do it here.  so this is cleaner and
   542	// shorter and less complicated.
   543	// The result of inlnode MUST be assigned back to n, e.g.
   544	// 	n.Left = inlnode(n.Left)
   545	func inlnode(n *Node, maxCost int32) *Node {
   546		if n == nil {
   547			return n
   548		}
   549	
   550		switch n.Op {
   551		// inhibit inlining of their argument
   552		case ODEFER, OGO:
   553			switch n.Left.Op {
   554			case OCALLFUNC, OCALLMETH:
   555				n.Left.SetNoInline(true)
   556			}
   557			return n
   558	
   559		// TODO do them here (or earlier),
   560		// so escape analysis can avoid more heapmoves.
   561		case OCLOSURE:
   562			return n
   563		}
   564	
   565		lno := setlineno(n)
   566	
   567		inlnodelist(n.Ninit, maxCost)
   568		for _, n1 := range n.Ninit.Slice() {
   569			if n1.Op == OINLCALL {
   570				inlconv2stmt(n1)
   571			}
   572		}
   573	
   574		n.Left = inlnode(n.Left, maxCost)
   575		if n.Left != nil && n.Left.Op == OINLCALL {
   576			n.Left = inlconv2expr(n.Left)
   577		}
   578	
   579		n.Right = inlnode(n.Right, maxCost)
   580		if n.Right != nil && n.Right.Op == OINLCALL {
   581			if n.Op == OFOR || n.Op == OFORUNTIL {
   582				inlconv2stmt(n.Right)
   583			} else {
   584				n.Right = inlconv2expr(n.Right)
   585			}
   586		}
   587	
   588		inlnodelist(n.List, maxCost)
   589		if n.Op == OBLOCK {
   590			for _, n2 := range n.List.Slice() {
   591				if n2.Op == OINLCALL {
   592					inlconv2stmt(n2)
   593				}
   594			}
   595		} else {
   596			s := n.List.Slice()
   597			for i1, n1 := range s {
   598				if n1 != nil && n1.Op == OINLCALL {
   599					s[i1] = inlconv2expr(s[i1])
   600				}
   601			}
   602		}
   603	
   604		inlnodelist(n.Rlist, maxCost)
   605		if n.Op == OAS2FUNC && n.Rlist.First().Op == OINLCALL {
   606			n.Rlist.Set(inlconv2list(n.Rlist.First()))
   607			n.Op = OAS2
   608			n.SetTypecheck(0)
   609			n = typecheck(n, ctxStmt)
   610		} else {
   611			s := n.Rlist.Slice()
   612			for i1, n1 := range s {
   613				if n1.Op == OINLCALL {
   614					if n.Op == OIF {
   615						inlconv2stmt(n1)
   616					} else {
   617						s[i1] = inlconv2expr(s[i1])
   618					}
   619				}
   620			}
   621		}
   622	
   623		inlnodelist(n.Nbody, maxCost)
   624		for _, n := range n.Nbody.Slice() {
   625			if n.Op == OINLCALL {
   626				inlconv2stmt(n)
   627			}
   628		}
   629	
   630		// with all the branches out of the way, it is now time to
   631		// transmogrify this node itself unless inhibited by the
   632		// switch at the top of this function.
   633		switch n.Op {
   634		case OCALLFUNC, OCALLMETH:
   635			if n.NoInline() {
   636				return n
   637			}
   638		}
   639	
   640		switch n.Op {
   641		case OCALLFUNC:
   642			if Debug['m'] > 3 {
   643				fmt.Printf("%v:call to func %+v\n", n.Line(), n.Left)
   644			}
   645			if n.Left.Func != nil && n.Left.Func.Inl != nil && !isIntrinsicCall(n) { // normal case
   646				n = mkinlcall(n, n.Left, maxCost)
   647			} else if n.Left.isMethodExpression() && asNode(n.Left.Sym.Def) != nil {
   648				n = mkinlcall(n, asNode(n.Left.Sym.Def), maxCost)
   649			} else if n.Left.Op == OCLOSURE {
   650				if f := inlinableClosure(n.Left); f != nil {
   651					n = mkinlcall(n, f, maxCost)
   652				}
   653			} else if n.Left.Op == ONAME && n.Left.Name != nil && n.Left.Name.Defn != nil {
   654				if d := n.Left.Name.Defn; d.Op == OAS && d.Right.Op == OCLOSURE {
   655					if f := inlinableClosure(d.Right); f != nil {
   656						// NB: this check is necessary to prevent indirect re-assignment of the variable
   657						// having the address taken after the invocation or only used for reads is actually fine
   658						// but we have no easy way to distinguish the safe cases
   659						if d.Left.Addrtaken() {
   660							if Debug['m'] > 1 {
   661								fmt.Printf("%v: cannot inline escaping closure variable %v\n", n.Line(), n.Left)
   662							}
   663							break
   664						}
   665	
   666						// ensure the variable is never re-assigned
   667						if unsafe, a := reassigned(n.Left); unsafe {
   668							if Debug['m'] > 1 {
   669								if a != nil {
   670									fmt.Printf("%v: cannot inline re-assigned closure variable at %v: %v\n", n.Line(), a.Line(), a)
   671								} else {
   672									fmt.Printf("%v: cannot inline global closure variable %v\n", n.Line(), n.Left)
   673								}
   674							}
   675							break
   676						}
   677						n = mkinlcall(n, f, maxCost)
   678					}
   679				}
   680			}
   681	
   682		case OCALLMETH:
   683			if Debug['m'] > 3 {
   684				fmt.Printf("%v:call to meth %L\n", n.Line(), n.Left.Right)
   685			}
   686	
   687			// typecheck should have resolved ODOTMETH->type, whose nname points to the actual function.
   688			if n.Left.Type == nil {
   689				Fatalf("no function type for [%p] %+v\n", n.Left, n.Left)
   690			}
   691	
   692			if n.Left.Type.Nname() == nil {
   693				Fatalf("no function definition for [%p] %+v\n", n.Left.Type, n.Left.Type)
   694			}
   695	
   696			n = mkinlcall(n, asNode(n.Left.Type.FuncType().Nname), maxCost)
   697		}
   698	
   699		lineno = lno
   700		return n
   701	}
   702	
   703	// inlinableClosure takes an OCLOSURE node and follows linkage to the matching ONAME with
   704	// the inlinable body. Returns nil if the function is not inlinable.
   705	func inlinableClosure(n *Node) *Node {
   706		c := n.Func.Closure
   707		caninl(c)
   708		f := c.Func.Nname
   709		if f == nil || f.Func.Inl == nil {
   710			return nil
   711		}
   712		return f
   713	}
   714	
   715	// reassigned takes an ONAME node, walks the function in which it is defined, and returns a boolean
   716	// indicating whether the name has any assignments other than its declaration.
   717	// The second return value is the first such assignment encountered in the walk, if any. It is mostly
   718	// useful for -m output documenting the reason for inhibited optimizations.
   719	// NB: global variables are always considered to be re-assigned.
   720	// TODO: handle initial declaration not including an assignment and followed by a single assignment?
   721	func reassigned(n *Node) (bool, *Node) {
   722		if n.Op != ONAME {
   723			Fatalf("reassigned %v", n)
   724		}
   725		// no way to reliably check for no-reassignment of globals, assume it can be
   726		if n.Name.Curfn == nil {
   727			return true, nil
   728		}
   729		f := n.Name.Curfn
   730		// There just might be a good reason for this although this can be pretty surprising:
   731		// local variables inside a closure have Curfn pointing to the OCLOSURE node instead
   732		// of the corresponding ODCLFUNC.
   733		// We need to walk the function body to check for reassignments so we follow the
   734		// linkage to the ODCLFUNC node as that is where body is held.
   735		if f.Op == OCLOSURE {
   736			f = f.Func.Closure
   737		}
   738		v := reassignVisitor{name: n}
   739		a := v.visitList(f.Nbody)
   740		return a != nil, a
   741	}
   742	
   743	type reassignVisitor struct {
   744		name *Node
   745	}
   746	
   747	func (v *reassignVisitor) visit(n *Node) *Node {
   748		if n == nil {
   749			return nil
   750		}
   751		switch n.Op {
   752		case OAS:
   753			if n.Left == v.name && n != v.name.Name.Defn {
   754				return n
   755			}
   756			return nil
   757		case OAS2, OAS2FUNC, OAS2MAPR, OAS2DOTTYPE:
   758			for _, p := range n.List.Slice() {
   759				if p == v.name && n != v.name.Name.Defn {
   760					return n
   761				}
   762			}
   763			return nil
   764		}
   765		if a := v.visit(n.Left); a != nil {
   766			return a
   767		}
   768		if a := v.visit(n.Right); a != nil {
   769			return a
   770		}
   771		if a := v.visitList(n.List); a != nil {
   772			return a
   773		}
   774		if a := v.visitList(n.Rlist); a != nil {
   775			return a
   776		}
   777		if a := v.visitList(n.Ninit); a != nil {
   778			return a
   779		}
   780		if a := v.visitList(n.Nbody); a != nil {
   781			return a
   782		}
   783		return nil
   784	}
   785	
   786	func (v *reassignVisitor) visitList(l Nodes) *Node {
   787		for _, n := range l.Slice() {
   788			if a := v.visit(n); a != nil {
   789				return a
   790			}
   791		}
   792		return nil
   793	}
   794	
   795	func tinlvar(t *types.Field, inlvars map[*Node]*Node) *Node {
   796		if n := asNode(t.Nname); n != nil && !n.isBlank() {
   797			inlvar := inlvars[n]
   798			if inlvar == nil {
   799				Fatalf("missing inlvar for %v\n", n)
   800			}
   801			return inlvar
   802		}
   803	
   804		return typecheck(nblank, ctxExpr|ctxAssign)
   805	}
   806	
   807	var inlgen int
   808	
   809	// If n is a call, and fn is a function with an inlinable body,
   810	// return an OINLCALL.
   811	// On return ninit has the parameter assignments, the nbody is the
   812	// inlined function body and list, rlist contain the input, output
   813	// parameters.
   814	// The result of mkinlcall MUST be assigned back to n, e.g.
   815	// 	n.Left = mkinlcall(n.Left, fn, isddd)
   816	func mkinlcall(n, fn *Node, maxCost int32) *Node {
   817		if fn.Func.Inl == nil {
   818			// No inlinable body.
   819			return n
   820		}
   821		if fn.Func.Inl.Cost > maxCost {
   822			// The inlined function body is too big. Typically we use this check to restrict
   823			// inlining into very big functions.  See issue 26546 and 17566.
   824			return n
   825		}
   826	
   827		if fn == Curfn || fn.Name.Defn == Curfn {
   828			// Can't recursively inline a function into itself.
   829			return n
   830		}
   831	
   832		if instrumenting && isRuntimePkg(fn.Sym.Pkg) {
   833			// Runtime package must not be instrumented.
   834			// Instrument skips runtime package. However, some runtime code can be
   835			// inlined into other packages and instrumented there. To avoid this,
   836			// we disable inlining of runtime functions when instrumenting.
   837			// The example that we observed is inlining of LockOSThread,
   838			// which lead to false race reports on m contents.
   839			return n
   840		}
   841	
   842		if Debug_typecheckinl == 0 {
   843			typecheckinl(fn)
   844		}
   845	
   846		// We have a function node, and it has an inlineable body.
   847		if Debug['m'] > 1 {
   848			fmt.Printf("%v: inlining call to %v %#v { %#v }\n", n.Line(), fn.Sym, fn.Type, asNodes(fn.Func.Inl.Body))
   849		} else if Debug['m'] != 0 {
   850			fmt.Printf("%v: inlining call to %v\n", n.Line(), fn)
   851		}
   852		if Debug['m'] > 2 {
   853			fmt.Printf("%v: Before inlining: %+v\n", n.Line(), n)
   854		}
   855	
   856		if ssaDump != "" && ssaDump == Curfn.funcname() {
   857			ssaDumpInlined = append(ssaDumpInlined, fn)
   858		}
   859	
   860		ninit := n.Ninit
   861	
   862		// Make temp names to use instead of the originals.
   863		inlvars := make(map[*Node]*Node)
   864	
   865		// record formals/locals for later post-processing
   866		var inlfvars []*Node
   867	
   868		// Handle captured variables when inlining closures.
   869		if fn.Name.Defn != nil {
   870			if c := fn.Name.Defn.Func.Closure; c != nil {
   871				for _, v := range c.Func.Closure.Func.Cvars.Slice() {
   872					if v.Op == OXXX {
   873						continue
   874					}
   875	
   876					o := v.Name.Param.Outer
   877					// make sure the outer param matches the inlining location
   878					// NB: if we enabled inlining of functions containing OCLOSURE or refined
   879					// the reassigned check via some sort of copy propagation this would most
   880					// likely need to be changed to a loop to walk up to the correct Param
   881					if o == nil || (o.Name.Curfn != Curfn && o.Name.Curfn.Func.Closure != Curfn) {
   882						Fatalf("%v: unresolvable capture %v %v\n", n.Line(), fn, v)
   883					}
   884	
   885					if v.Name.Byval() {
   886						iv := typecheck(inlvar(v), ctxExpr)
   887						ninit.Append(nod(ODCL, iv, nil))
   888						ninit.Append(typecheck(nod(OAS, iv, o), ctxStmt))
   889						inlvars[v] = iv
   890					} else {
   891						addr := newname(lookup("&" + v.Sym.Name))
   892						addr.Type = types.NewPtr(v.Type)
   893						ia := typecheck(inlvar(addr), ctxExpr)
   894						ninit.Append(nod(ODCL, ia, nil))
   895						ninit.Append(typecheck(nod(OAS, ia, nod(OADDR, o, nil)), ctxStmt))
   896						inlvars[addr] = ia
   897	
   898						// When capturing by reference, all occurrence of the captured var
   899						// must be substituted with dereference of the temporary address
   900						inlvars[v] = typecheck(nod(ODEREF, ia, nil), ctxExpr)
   901					}
   902				}
   903			}
   904		}
   905	
   906		for _, ln := range fn.Func.Inl.Dcl {
   907			if ln.Op != ONAME {
   908				continue
   909			}
   910			if ln.Class() == PPARAMOUT { // return values handled below.
   911				continue
   912			}
   913			if ln.isParamStackCopy() { // ignore the on-stack copy of a parameter that moved to the heap
   914				continue
   915			}
   916			inlvars[ln] = typecheck(inlvar(ln), ctxExpr)
   917			if ln.Class() == PPARAM || ln.Name.Param.Stackcopy != nil && ln.Name.Param.Stackcopy.Class() == PPARAM {
   918				ninit.Append(nod(ODCL, inlvars[ln], nil))
   919			}
   920			if genDwarfInline > 0 {
   921				inlf := inlvars[ln]
   922				if ln.Class() == PPARAM {
   923					inlf.SetInlFormal(true)
   924				} else {
   925					inlf.SetInlLocal(true)
   926				}
   927				inlf.Pos = ln.Pos
   928				inlfvars = append(inlfvars, inlf)
   929			}
   930		}
   931	
   932		// temporaries for return values.
   933		var retvars []*Node
   934		for i, t := range fn.Type.Results().Fields().Slice() {
   935			var m *Node
   936			mpos := t.Pos
   937			if n := asNode(t.Nname); n != nil && !n.isBlank() {
   938				m = inlvar(n)
   939				m = typecheck(m, ctxExpr)
   940				inlvars[n] = m
   941			} else {
   942				// anonymous return values, synthesize names for use in assignment that replaces return
   943				m = retvar(t, i)
   944			}
   945	
   946			if genDwarfInline > 0 {
   947				// Don't update the src.Pos on a return variable if it
   948				// was manufactured by the inliner (e.g. "~R2"); such vars
   949				// were not part of the original callee.
   950				if !strings.HasPrefix(m.Sym.Name, "~R") {
   951					m.SetInlFormal(true)
   952					m.Pos = mpos
   953					inlfvars = append(inlfvars, m)
   954				}
   955			}
   956	
   957			ninit.Append(nod(ODCL, m, nil))
   958			retvars = append(retvars, m)
   959		}
   960	
   961		// Assign arguments to the parameters' temp names.
   962		as := nod(OAS2, nil, nil)
   963		as.Rlist.Set(n.List.Slice())
   964	
   965		// For non-dotted calls to variadic functions, we assign the
   966		// variadic parameter's temp name separately.
   967		var vas *Node
   968	
   969		if fn.IsMethod() {
   970			rcv := fn.Type.Recv()
   971	
   972			if n.Left.Op == ODOTMETH {
   973				// For x.M(...), assign x directly to the
   974				// receiver parameter.
   975				if n.Left.Left == nil {
   976					Fatalf("method call without receiver: %+v", n)
   977				}
   978				ras := nod(OAS, tinlvar(rcv, inlvars), n.Left.Left)
   979				ras = typecheck(ras, ctxStmt)
   980				ninit.Append(ras)
   981			} else {
   982				// For T.M(...), add the receiver parameter to
   983				// as.List, so it's assigned by the normal
   984				// arguments.
   985				if as.Rlist.Len() == 0 {
   986					Fatalf("non-method call to method without first arg: %+v", n)
   987				}
   988				as.List.Append(tinlvar(rcv, inlvars))
   989			}
   990		}
   991	
   992		for _, param := range fn.Type.Params().Fields().Slice() {
   993			// For ordinary parameters or variadic parameters in
   994			// dotted calls, just add the variable to the
   995			// assignment list, and we're done.
   996			if !param.IsDDD() || n.IsDDD() {
   997				as.List.Append(tinlvar(param, inlvars))
   998				continue
   999			}
  1000	
  1001			// Otherwise, we need to collect the remaining values
  1002			// to pass as a slice.
  1003	
  1004			numvals := n.List.Len()
  1005	
  1006			x := as.List.Len()
  1007			for as.List.Len() < numvals {
  1008				as.List.Append(argvar(param.Type, as.List.Len()))
  1009			}
  1010			varargs := as.List.Slice()[x:]
  1011	
  1012			vas = nod(OAS, tinlvar(param, inlvars), nil)
  1013			if len(varargs) == 0 {
  1014				vas.Right = nodnil()
  1015				vas.Right.Type = param.Type
  1016			} else {
  1017				vas.Right = nod(OCOMPLIT, nil, typenod(param.Type))
  1018				vas.Right.List.Set(varargs)
  1019			}
  1020		}
  1021	
  1022		if as.Rlist.Len() != 0 {
  1023			as = typecheck(as, ctxStmt)
  1024			ninit.Append(as)
  1025		}
  1026	
  1027		if vas != nil {
  1028			vas = typecheck(vas, ctxStmt)
  1029			ninit.Append(vas)
  1030		}
  1031	
  1032		// Zero the return parameters.
  1033		for _, n := range retvars {
  1034			ras := nod(OAS, n, nil)
  1035			ras = typecheck(ras, ctxStmt)
  1036			ninit.Append(ras)
  1037		}
  1038	
  1039		retlabel := autolabel(".i")
  1040	
  1041		inlgen++
  1042	
  1043		parent := -1
  1044		if b := Ctxt.PosTable.Pos(n.Pos).Base(); b != nil {
  1045			parent = b.InliningIndex()
  1046		}
  1047		newIndex := Ctxt.InlTree.Add(parent, n.Pos, fn.Sym.Linksym())
  1048	
  1049		// Add an inline mark just before the inlined body.
  1050		// This mark is inline in the code so that it's a reasonable spot
  1051		// to put a breakpoint. Not sure if that's really necessary or not
  1052		// (in which case it could go at the end of the function instead).
  1053		// Note issue 28603.
  1054		inlMark := nod(OINLMARK, nil, nil)
  1055		inlMark.Pos = n.Pos.WithIsStmt()
  1056		inlMark.Xoffset = int64(newIndex)
  1057		ninit.Append(inlMark)
  1058	
  1059		if genDwarfInline > 0 {
  1060			if !fn.Sym.Linksym().WasInlined() {
  1061				Ctxt.DwFixups.SetPrecursorFunc(fn.Sym.Linksym(), fn)
  1062				fn.Sym.Linksym().Set(obj.AttrWasInlined, true)
  1063			}
  1064		}
  1065	
  1066		subst := inlsubst{
  1067			retlabel:    retlabel,
  1068			retvars:     retvars,
  1069			inlvars:     inlvars,
  1070			bases:       make(map[*src.PosBase]*src.PosBase),
  1071			newInlIndex: newIndex,
  1072		}
  1073	
  1074		body := subst.list(asNodes(fn.Func.Inl.Body))
  1075	
  1076		lab := nodSym(OLABEL, nil, retlabel)
  1077		body = append(body, lab)
  1078	
  1079		typecheckslice(body, ctxStmt)
  1080	
  1081		if genDwarfInline > 0 {
  1082			for _, v := range inlfvars {
  1083				v.Pos = subst.updatedPos(v.Pos)
  1084			}
  1085		}
  1086	
  1087		//dumplist("ninit post", ninit);
  1088	
  1089		call := nod(OINLCALL, nil, nil)
  1090		call.Ninit.Set(ninit.Slice())
  1091		call.Nbody.Set(body)
  1092		call.Rlist.Set(retvars)
  1093		call.Type = n.Type
  1094		call.SetTypecheck(1)
  1095	
  1096		// transitive inlining
  1097		// might be nice to do this before exporting the body,
  1098		// but can't emit the body with inlining expanded.
  1099		// instead we emit the things that the body needs
  1100		// and each use must redo the inlining.
  1101		// luckily these are small.
  1102		inlnodelist(call.Nbody, maxCost)
  1103		for _, n := range call.Nbody.Slice() {
  1104			if n.Op == OINLCALL {
  1105				inlconv2stmt(n)
  1106			}
  1107		}
  1108	
  1109		if Debug['m'] > 2 {
  1110			fmt.Printf("%v: After inlining %+v\n\n", call.Line(), call)
  1111		}
  1112	
  1113		return call
  1114	}
  1115	
  1116	// Every time we expand a function we generate a new set of tmpnames,
  1117	// PAUTO's in the calling functions, and link them off of the
  1118	// PPARAM's, PAUTOS and PPARAMOUTs of the called function.
  1119	func inlvar(var_ *Node) *Node {
  1120		if Debug['m'] > 3 {
  1121			fmt.Printf("inlvar %+v\n", var_)
  1122		}
  1123	
  1124		n := newname(var_.Sym)
  1125		n.Type = var_.Type
  1126		n.SetClass(PAUTO)
  1127		n.Name.SetUsed(true)
  1128		n.Name.Curfn = Curfn // the calling function, not the called one
  1129		n.SetAddrtaken(var_.Addrtaken())
  1130	
  1131		Curfn.Func.Dcl = append(Curfn.Func.Dcl, n)
  1132		return n
  1133	}
  1134	
  1135	// Synthesize a variable to store the inlined function's results in.
  1136	func retvar(t *types.Field, i int) *Node {
  1137		n := newname(lookupN("~R", i))
  1138		n.Type = t.Type
  1139		n.SetClass(PAUTO)
  1140		n.Name.SetUsed(true)
  1141		n.Name.Curfn = Curfn // the calling function, not the called one
  1142		Curfn.Func.Dcl = append(Curfn.Func.Dcl, n)
  1143		return n
  1144	}
  1145	
  1146	// Synthesize a variable to store the inlined function's arguments
  1147	// when they come from a multiple return call.
  1148	func argvar(t *types.Type, i int) *Node {
  1149		n := newname(lookupN("~arg", i))
  1150		n.Type = t.Elem()
  1151		n.SetClass(PAUTO)
  1152		n.Name.SetUsed(true)
  1153		n.Name.Curfn = Curfn // the calling function, not the called one
  1154		Curfn.Func.Dcl = append(Curfn.Func.Dcl, n)
  1155		return n
  1156	}
  1157	
  1158	// The inlsubst type implements the actual inlining of a single
  1159	// function call.
  1160	type inlsubst struct {
  1161		// Target of the goto substituted in place of a return.
  1162		retlabel *types.Sym
  1163	
  1164		// Temporary result variables.
  1165		retvars []*Node
  1166	
  1167		inlvars map[*Node]*Node
  1168	
  1169		// bases maps from original PosBase to PosBase with an extra
  1170		// inlined call frame.
  1171		bases map[*src.PosBase]*src.PosBase
  1172	
  1173		// newInlIndex is the index of the inlined call frame to
  1174		// insert for inlined nodes.
  1175		newInlIndex int
  1176	}
  1177	
  1178	// list inlines a list of nodes.
  1179	func (subst *inlsubst) list(ll Nodes) []*Node {
  1180		s := make([]*Node, 0, ll.Len())
  1181		for _, n := range ll.Slice() {
  1182			s = append(s, subst.node(n))
  1183		}
  1184		return s
  1185	}
  1186	
  1187	// node recursively copies a node from the saved pristine body of the
  1188	// inlined function, substituting references to input/output
  1189	// parameters with ones to the tmpnames, and substituting returns with
  1190	// assignments to the output.
  1191	func (subst *inlsubst) node(n *Node) *Node {
  1192		if n == nil {
  1193			return nil
  1194		}
  1195	
  1196		switch n.Op {
  1197		case ONAME:
  1198			if inlvar := subst.inlvars[n]; inlvar != nil { // These will be set during inlnode
  1199				if Debug['m'] > 2 {
  1200					fmt.Printf("substituting name %+v  ->  %+v\n", n, inlvar)
  1201				}
  1202				return inlvar
  1203			}
  1204	
  1205			if Debug['m'] > 2 {
  1206				fmt.Printf("not substituting name %+v\n", n)
  1207			}
  1208			return n
  1209	
  1210		case OLITERAL, OTYPE:
  1211			// If n is a named constant or type, we can continue
  1212			// using it in the inline copy. Otherwise, make a copy
  1213			// so we can update the line number.
  1214			if n.Sym != nil {
  1215				return n
  1216			}
  1217	
  1218			// Since we don't handle bodies with closures, this return is guaranteed to belong to the current inlined function.
  1219	
  1220		//		dump("Return before substitution", n);
  1221		case ORETURN:
  1222			m := nodSym(OGOTO, nil, subst.retlabel)
  1223			m.Ninit.Set(subst.list(n.Ninit))
  1224	
  1225			if len(subst.retvars) != 0 && n.List.Len() != 0 {
  1226				as := nod(OAS2, nil, nil)
  1227	
  1228				// Make a shallow copy of retvars.
  1229				// Otherwise OINLCALL.Rlist will be the same list,
  1230				// and later walk and typecheck may clobber it.
  1231				for _, n := range subst.retvars {
  1232					as.List.Append(n)
  1233				}
  1234				as.Rlist.Set(subst.list(n.List))
  1235				as = typecheck(as, ctxStmt)
  1236				m.Ninit.Append(as)
  1237			}
  1238	
  1239			typecheckslice(m.Ninit.Slice(), ctxStmt)
  1240			m = typecheck(m, ctxStmt)
  1241	
  1242			//		dump("Return after substitution", m);
  1243			return m
  1244	
  1245		case OGOTO, OLABEL:
  1246			m := n.copy()
  1247			m.Pos = subst.updatedPos(m.Pos)
  1248			m.Ninit.Set(nil)
  1249			p := fmt.Sprintf("%s·%d", n.Sym.Name, inlgen)
  1250			m.Sym = lookup(p)
  1251	
  1252			return m
  1253		}
  1254	
  1255		m := n.copy()
  1256		m.Pos = subst.updatedPos(m.Pos)
  1257		m.Ninit.Set(nil)
  1258	
  1259		if n.Op == OCLOSURE {
  1260			Fatalf("cannot inline function containing closure: %+v", n)
  1261		}
  1262	
  1263		m.Left = subst.node(n.Left)
  1264		m.Right = subst.node(n.Right)
  1265		m.List.Set(subst.list(n.List))
  1266		m.Rlist.Set(subst.list(n.Rlist))
  1267		m.Ninit.Set(append(m.Ninit.Slice(), subst.list(n.Ninit)...))
  1268		m.Nbody.Set(subst.list(n.Nbody))
  1269	
  1270		return m
  1271	}
  1272	
  1273	func (subst *inlsubst) updatedPos(xpos src.XPos) src.XPos {
  1274		pos := Ctxt.PosTable.Pos(xpos)
  1275		oldbase := pos.Base() // can be nil
  1276		newbase := subst.bases[oldbase]
  1277		if newbase == nil {
  1278			newbase = src.NewInliningBase(oldbase, subst.newInlIndex)
  1279			subst.bases[oldbase] = newbase
  1280		}
  1281		pos.SetBase(newbase)
  1282		return Ctxt.PosTable.XPos(pos)
  1283	}
  1284	
  1285	func pruneUnusedAutos(ll []*Node, vis *hairyVisitor) []*Node {
  1286		s := make([]*Node, 0, len(ll))
  1287		for _, n := range ll {
  1288			if n.Class() == PAUTO {
  1289				if _, found := vis.usedLocals[n]; !found {
  1290					continue
  1291				}
  1292			}
  1293			s = append(s, n)
  1294		}
  1295		return s
  1296	}
  1297	

View as plain text