Go compilation principle series 9 (function inlining)

前言

The variable capture part of compiler optimization was shared in the previous article,This article shares another aspect of compiler optimization—函数内联.Function inlining means that the contents of a smaller function will be inlined,directly into the caller function,Thereby reducing the overhead of function calls

Overview of function inlining

We know the function calls of every high-level programming language,The cost is related to the need to allocate stack memory for it to store parameters、返回值、局部变量等等,GoThe cost of the function call lies in Parameter and return value stack copy、Small stack register overhead以及Check stack expansion in function prologue（Go语言中的栈是可以动态扩容的,因为GoThe memory on the allocation stack is not incrementally increased,Rather, it is a one-time allocation,This is to avoid accessing out of bounds,It will be allocated all at once,When it is checked that the allocated stack memory is not enough,It will expand a sufficiently large stack space,and copy the contents of the original stack）

Write a piece of code below,通过GoThe benchmark test to measure the efficiency improvement brought by function inlining

import "testing"

//go:noinline //禁用内联.If you want to enable inline,Just uncomment this line
func max(a, b int) int {
 if a > b {
  return a
 }

 return b
}

var Result int
func BenchmarkMax(b *testing.B)  {
 var r int
 for i:=0; i< b.N; i++ {
  r = max(-1, i)
 }
 Result = r
}

在编译的过程中,GoThe compiler actually calculates the cost of function inlining,So there are only simple functions,function inlining will be triggered.In the source code implementation of the following function inlining,We can see these situations below不会被内联：

• 递归函数
• The function is preceded by the following comment： go:noinline、 go:norace、 go:nocheckptr、 go:uintptrescapes等
• 没有函数体
• The number of nodes in the abstract syntax tree of the function declaration is greater than5000（我的Go版本是1.16.6）（That is, there are too many statements inside the function,Nor will it be inlined）
• Functions contain closures（* OCLOSURE）、range（ORANGE）、select（OSELECT）、go（OGO）、defer（ODEFER）、type（ODCLTYPE）、返回值是函数（ORETJMP*）的,will not inline

We can also build or compile time,Controls whether it can be inlined through parameters.If you don't want all the functions in the program to be inlined

go build -gcflags="-l" xxx.go
go tool compile -l xxx.go

Also we are at compile time,You can also see which functions are inlined,Which functions are not inlined,以及原因是什么

go tool compile -m=2 xxx.go

看一个例子

package main

func test1(a, b int) int {
 return a+b
}

func step(n int) int {
 if n < 2 {
  return n
 }
 return step(n-1) + step(n-2)
}

func main()  {
 test1(1, 2)
 step(5)
}

可以看到test1This function can be inlined,Because its function body is very simple.stepThis function is a recursive function,So it doesn't do inlining

The underlying implementation of function inlining

In fact, each function call chain is very deep here,I will not explain the meaning of the code line by line here,Only some core methods will be introduced,Interested friends can debug it themselves(There are related articles posted earlier)（Go源码调试方法）

It was mentioned many times beforeGo编译入口文件,You can find this code in the entry file

Go编译入口文件：src/cmd/compile/main.go -> gc.Main(archInit)

// Phase 5: Inlining
if Debug.l != 0 {
  // Find functions that can be inlined
  visitBottomUp(xtop, func(list []*Node, recursive bool) {
   numfns := numNonClosures(list)
   for _, n := range list {
    if !recursive || numfns > 1 {
     caninl(n)
    } else {
     ......
    }
    inlcalls(n)
   }
  })
 }

 for _, n := range xtop {
  if n.Op == ODCLFUNC {
   devirtualize(n)
  }
 }

Let's take a look at what each method does

visitBottomUp

该方法有两个参数：

• xtop：I've seen it before,It stores the root node array of the abstract syntax tree of each declaration statement
• 第二个参数是一个函数（The function also has two parameters,One is an array of abstract syntax tree root nodes that satisfy the declaration of a function type,一个是bool值,trueRepresents a recursive function,falseIndicates that it is not a recursive function）

进入到visitBottomUp方法中,You'll find it's mostly traversalxtop,And called on the root node of each abstract syntax treevisit这个方法（Only for abstract syntax trees that are function type declarations）

func visitBottomUp(list []*Node, analyze func(list []*Node, recursive bool)) {
 var v bottomUpVisitor
 v.analyze = analyze
 v.nodeID = make(map[*Node]uint32)
 for _, n := range list {
  if n.Op == ODCLFUNC && !n.Func.IsHiddenClosure() { //是函数,and is not a closure function
   v.visit(n)
  }
 }
}

而visit方法的核心是调用了inspectList方法,通过inspectListThe abstract syntax tree is traversed in a depth-first search,and take each node as inspectList方法的第二个参数（是一个函数）的参数,For example, to verify whether there are recursive calls in this function, etc（Specifically belowswitch case）

func (v *bottomUpVisitor) visit(n *Node) uint32 {
 if id := v.nodeID[n]; id > 0 {
  // already visited
  return id
 }

 ......
 v.stack = append(v.stack, n)

 inspectList(n.Nbody, func(n *Node) bool {
  switch n.Op {
  case ONAME:
   if n.Class() == PFUNC {
    ......
   }
  case ODOTMETH:
   fn := asNode(n.Type.Nname())
   ......
   }
  case OCALLPART:
   fn := asNode(callpartMethod(n).Type.Nname())
   ......
  case OCLOSURE:
   if m := v.visit(n.Func.Closure); m < min {
    min = m
   }
  }
  return true
 })
  v.analyze(block, recursive)
 }

 return min
}

By calling latervisitBottomUpThe method passed as the second parameter,Perform inline judgment and inline operations on abstract syntax trees,具体就是caninl和inlcalls这两个方法

caninl

The role of this method is to verify whether the abstract syntax tree declared by the function type can be inlined

这个方法的实现很简单,The first is through a lotifThe statement verifies whether there is an image in front of the functiongo:noinlinewait for this mark

func caninl(fn *Node) {
 if fn.Op != ODCLFUNC {
  Fatalf("caninl %v", fn)
 }
 if fn.Func.Nname == nil {
  Fatalf("caninl no nname %+v", fn)
 }

 var reason string // reason, if any, that the function was not inlined
 ......

 // If marked "go:noinline", don't inline
 if fn.Func.Pragma&Noinline != 0 {
  reason = "marked go:noinline"
  return
 }

 // If marked "go:norace" and -race compilation, don't inline.
 if flag_race && fn.Func.Pragma&Norace != 0 {
  reason = "marked go:norace with -race compilation"
  return
 }

 ......

 // If fn has no body (is defined outside of Go), cannot inline it.
 if fn.Nbody.Len() == 0 {
  reason = "no function body"
  return
 }

 visitor := hairyVisitor{
  budget:        inlineMaxBudget,
  extraCallCost: cc,
  usedLocals:    make(map[*Node]bool),
 }
 if visitor.visitList(fn.Nbody) {
  reason = visitor.reason
  return
 }
 if visitor.budget < 0 {
  reason = fmt.Sprintf("function too complex: cost %d exceeds budget %d", inlineMaxBudget-visitor.budget, inlineMaxBudget)
  return
 }

 n.Func.Inl = &Inline{
  Cost: inlineMaxBudget - visitor.budget,
  Dcl:  inlcopylist(pruneUnusedAutos(n.Name.Defn.Func.Dcl, &visitor)),
  Body: inlcopylist(fn.Nbody.Slice()),
 }
 ......
}

There is another main method herevisitList,It is used to verify whether the function we mentioned above is in itgo、select、rangeWait for these sentences.For inline conditions,It will override the function declaration to free the inline field of the syntax tree(Inl)

inlcalls

This method is the specific inline operation,For example, converting the parameters and return values ​​of the function into declaration statements in the caller, etc.The calls and implementations inside are more complicated,No more sticking code here,You can see for yourself.The core methods of function inlining are in the following files

src/cmd/compile/internal/gc/inl.go