interleaved.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 interleaved implements the interleaved devirtualization and
     6  // inlining pass.
     7  package interleaved
     8  
     9  import (
    10  	"cmd/compile/internal/base"
    11  	"cmd/compile/internal/devirtualize"
    12  	"cmd/compile/internal/inline"
    13  	"cmd/compile/internal/inline/inlheur"
    14  	"cmd/compile/internal/ir"
    15  	"cmd/compile/internal/pgoir"
    16  	"cmd/compile/internal/typecheck"
    17  	"fmt"
    18  )
    19  
    20  // DevirtualizeAndInlinePackage interleaves devirtualization and inlining on
    21  // all functions within pkg.
    22  func DevirtualizeAndInlinePackage(pkg *ir.Package, profile *pgoir.Profile) {
    23  	if profile != nil && base.Debug.PGODevirtualize > 0 {
    24  		// TODO(mdempsky): Integrate into DevirtualizeAndInlineFunc below.
    25  		ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) {
    26  			for _, fn := range list {
    27  				devirtualize.ProfileGuided(fn, profile)
    28  			}
    29  		})
    30  		ir.CurFunc = nil
    31  	}
    32  
    33  	if base.Flag.LowerL != 0 {
    34  		inlheur.SetupScoreAdjustments()
    35  	}
    36  
    37  	var inlProfile *pgoir.Profile // copy of profile for inlining
    38  	if base.Debug.PGOInline != 0 {
    39  		inlProfile = profile
    40  	}
    41  
    42  	// First compute inlinability of all functions in the package.
    43  	inline.CanInlineFuncs(pkg.Funcs, inlProfile)
    44  
    45  	// Now we make a second pass to do devirtualization and inlining of
    46  	// calls. Order here should not matter.
    47  	for _, fn := range pkg.Funcs {
    48  		DevirtualizeAndInlineFunc(fn, inlProfile)
    49  	}
    50  
    51  	if base.Flag.LowerL != 0 {
    52  		// Perform a garbage collection of hidden closures functions that
    53  		// are no longer reachable from top-level functions following
    54  		// inlining. See #59404 and #59638 for more context.
    55  		inline.GarbageCollectUnreferencedHiddenClosures()
    56  
    57  		if base.Debug.DumpInlFuncProps != "" {
    58  			inlheur.DumpFuncProps(nil, base.Debug.DumpInlFuncProps)
    59  		}
    60  		if inlheur.Enabled() {
    61  			inline.PostProcessCallSites(inlProfile)
    62  			inlheur.TearDown()
    63  		}
    64  	}
    65  }
    66  
    67  // DevirtualizeAndInlineFunc interleaves devirtualization and inlining
    68  // on a single function.
    69  func DevirtualizeAndInlineFunc(fn *ir.Func, profile *pgoir.Profile) {
    70  	ir.WithFunc(fn, func() {
    71  		if base.Flag.LowerL != 0 {
    72  			if inlheur.Enabled() && !fn.Wrapper() {
    73  				inlheur.ScoreCalls(fn)
    74  				defer inlheur.ScoreCallsCleanup()
    75  			}
    76  			if base.Debug.DumpInlFuncProps != "" && !fn.Wrapper() {
    77  				inlheur.DumpFuncProps(fn, base.Debug.DumpInlFuncProps)
    78  			}
    79  		}
    80  
    81  		bigCaller := base.Flag.LowerL != 0 && inline.IsBigFunc(fn)
    82  		if bigCaller && base.Flag.LowerM > 1 {
    83  			fmt.Printf("%v: function %v considered 'big'; reducing max cost of inlinees\n", ir.Line(fn), fn)
    84  		}
    85  
    86  		match := func(n ir.Node) bool {
    87  			switch n := n.(type) {
    88  			case *ir.CallExpr:
    89  				return true
    90  			case *ir.TailCallStmt:
    91  				n.Call.NoInline = true // can't inline yet
    92  			}
    93  			return false
    94  		}
    95  
    96  		edit := func(n ir.Node) ir.Node {
    97  			call, ok := n.(*ir.CallExpr)
    98  			if !ok { // previously inlined
    99  				return nil
   100  			}
   101  
   102  			devirtualize.StaticCall(call)
   103  			if inlCall := inline.TryInlineCall(fn, call, bigCaller, profile); inlCall != nil {
   104  				return inlCall
   105  			}
   106  			return nil
   107  		}
   108  
   109  		fixpoint(fn, match, edit)
   110  	})
   111  }
   112  
   113  // fixpoint repeatedly edits a function until it stabilizes.
   114  //
   115  // First, fixpoint applies match to every node n within fn. Then it
   116  // iteratively applies edit to each node satisfying match(n).
   117  //
   118  // If edit(n) returns nil, no change is made. Otherwise, the result
   119  // replaces n in fn's body, and fixpoint iterates at least once more.
   120  //
   121  // After an iteration where all edit calls return nil, fixpoint
   122  // returns.
   123  func fixpoint(fn *ir.Func, match func(ir.Node) bool, edit func(ir.Node) ir.Node) {
   124  	// Consider the expression "f(g())". We want to be able to replace
   125  	// "g()" in-place with its inlined representation. But if we first
   126  	// replace "f(...)" with its inlined representation, then "g()" will
   127  	// instead appear somewhere within this new AST.
   128  	//
   129  	// To mitigate this, each matched node n is wrapped in a ParenExpr,
   130  	// so we can reliably replace n in-place by assigning ParenExpr.X.
   131  	// It's safe to use ParenExpr here, because typecheck already
   132  	// removed them all.
   133  
   134  	var parens []*ir.ParenExpr
   135  	var mark func(ir.Node) ir.Node
   136  	mark = func(n ir.Node) ir.Node {
   137  		if _, ok := n.(*ir.ParenExpr); ok {
   138  			return n // already visited n.X before wrapping
   139  		}
   140  
   141  		ok := match(n)
   142  
   143  		ir.EditChildren(n, mark)
   144  
   145  		if ok {
   146  			paren := ir.NewParenExpr(n.Pos(), n)
   147  			paren.SetType(n.Type())
   148  			paren.SetTypecheck(n.Typecheck())
   149  
   150  			parens = append(parens, paren)
   151  			n = paren
   152  		}
   153  
   154  		return n
   155  	}
   156  	ir.EditChildren(fn, mark)
   157  
   158  	// Edit until stable.
   159  	for {
   160  		done := true
   161  
   162  		for i := 0; i < len(parens); i++ { // can't use "range parens" here
   163  			paren := parens[i]
   164  			if new := edit(paren.X); new != nil {
   165  				// Update AST and recursively mark nodes.
   166  				paren.X = new
   167  				ir.EditChildren(new, mark) // mark may append to parens
   168  				done = false
   169  			}
   170  		}
   171  
   172  		if done {
   173  			break
   174  		}
   175  	}
   176  
   177  	// Finally, remove any parens we inserted.
   178  	if len(parens) == 0 {
   179  		return // short circuit
   180  	}
   181  	var unparen func(ir.Node) ir.Node
   182  	unparen = func(n ir.Node) ir.Node {
   183  		if paren, ok := n.(*ir.ParenExpr); ok {
   184  			n = paren.X
   185  		}
   186  		ir.EditChildren(n, unparen)
   187  		return n
   188  	}
   189  	ir.EditChildren(fn, unparen)
   190  }
   191
View as plain text