Smart Go compiler: Slimming

Smart Go compiler: Slimming

1. Experiment: Which Functions are Included in the Final Executable?

This article is first published in the medium MPP plan. If you are a medium user, please follow me in medium. Thank you very much.

Let’s conduct an experiment to determine which functions are included in the final executable! We’ll create a demo1 with the following directory structure and code snippets:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// dead-code-elimination/demo1
$ tree -F .
.
├── go.mod
├── main.go
└── pkga/
└── pkga.go

// main.go
package main

import (
"fmt"

"demo/pkga"
)

func main() {
result := pkga.Foo()
fmt.Println(result)
}

// pkga/pkga.go

package pkga

import (
"fmt"
)

func Foo() string {
return "Hello from Foo!"
}

func Bar() {
fmt.Println("This is Bar.")
}

The example is very simple! The main function calls the exported function Foo from the pkga package, which also contains the Bar function (although it is not called by any other function). Now let’s compile this module and examine the functions from the pkga package included in the compiled executable file! (This article uses Go version 1.22.0)

1
2
$ go build
$ go tool nm demo | grep demo

Surprisingly, we didn’t find any symbol information related to pkga in the output of the executable file. This might be due to Go’s optimization. Let’s disable the optimization of the Go compiler and try again:

1
2
3
$ go build -gcflags '-l -N'
$ go tool nm demo | grep demo
108ca80 T demo/pkga.Foo

After disabling inlining optimization, we can see that pkga.Foo appears in the final executable file demo, but the unused Bar function is not included.

Now let’s look at an example with indirect dependencies:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// dead-code-elimination/demo2
$ tree .
.
├── go.mod
├── main.go
├── pkga
│ └── pkga.go
└── pkgb
└── pkgb.go

// pkga/pkga.go
package pkga

import (
"demo/pkgb"
"fmt"
)

func Foo() string {
pkgb.Zoo()
return "Hello from Foo!"
}

func Bar() {
fmt.Println("This is Bar.")
}

In this example, we call a new function Zoo from the pkgb package within the pkga.Foo function. Let’s compile this new example and see which functions are included in the final executable:

1
2
3
4
$ go build -gcflags='-l -N'
$ go tool nm demo | grep demo
1093b40 T demo/pkga.Foo
1093aa0 T demo/pkgb.Zoo

We can observe that only the functions reachable through the program execution path are included in the final executable!

In more complex examples, we can use the go build -ldflags='-dumpdep' command to view the call dependency relationship (using demo2 as an example):

1
2
3
4
5
6
7
8
9
10
$ go build -ldflags='-dumpdep' -gcflags='-l -N' > deps.txt 2>&1

$ grep demo deps.txt
# demo
main.main -> demo/pkga.Foo
demo/pkga.Foo -> demo/pkgb.Zoo
demo/pkga.Foo -> go:string."Hello from Foo!"
demo/pkgb.Zoo -> math/rand.Int31n
demo/pkgb.Zoo -> demo/pkgb..stmp_0
demo/pkgb..stmp_0 -> go:string."Zoo in pkgb"

From this, we can conclude that Go ensures that only the code that is actually used enters the final executable file, even if some code (such as pkga.Bar) and the code that is actually used (such as pkga.Foo) are in the same package. This mechanism also ensures that the final executable file size remains within a manageable range.

Next, let’s explore this mechanism in Go.

2. Dead Code Elimination

Let’s review the build process of go build. The following steps outline the go build command:

  1. Read go.mod and go.sum: If the current directory contains a go.mod file, go build reads it to determine the project’s dependencies. It also verifies the integrity of the dependencies based on checksums in the go.sum file.
  2. Calculate the package dependency graph: go build analyzes the import statements in the packages being built and their dependencies to construct a dependency graph. This graph represents the relationships between packages, enabling the compiler to determine the build order of packages.
  3. Determine the packages to build: Based on the build cache and the dependency graph, go build determines which packages need to be built. It checks the build cache to see if the compiled packages are up to date. If any package or its dependencies have changed since the last build, go build will rebuild those packages.
  4. Invoke the compiler (go tool compile): For each package that needs to be built, go build invokes the Go compiler (go tool compile). The compiler converts the Go source code into machine code specific to the target platform and generates object files (.o files).
  5. Invoke the linker (go tool link): After compiling all the necessary packages, go build invokes the Go linker (go tool link). The linker merges the object files generated by the compiler into an executable binary file or a package archive file. It resolves symbols and references between packages, performs necessary relocations, and generates the final output.

The entire build process can be represented by the following diagram:

Build Process

During the build process, go build performs various optimizations, such as dead code elimination and inlining, to improve the performance and reduce the size of the generated binary files. Dead code elimination is an important mechanism that ensures the controllable size of the final executable file in Go.

The implementation of the dead code detection algorithm can be found in the $GOROOT/src/cmd/link/internal/ld/deadcode.go file. The algorithm operates by traversing the graph and follows these steps:

  1. Start from the entry point of the system and mark all symbols reachable through relocations. Relocation represents the dependency relationship between two symbols.
  2. By traversing the relocation relationships, the algorithm marks all symbols that can be accessed from the entry point. For example, if the function pkga.Foo is called in the main function main.main, there will be a relocation entry for this function in main.main.
  3. After marking is complete, the algorithm marks all unmarked symbols as unreachable and dead code. These unmarked symbols represent the code that cannot be accessed by the entry point or any other reachable symbols.

However, there is a special syntax element to note, which is types with methods. Whether the methods of a type are included in the final executable depends on different scenarios. In deadcode.go, the function implementation for marking reachable symbols distinguishes three cases of method invocation for reachable types:

  1. Direct invocation
  2. Invocation through reachable interface types
  3. Invocation through reflection: reflect.Value.Method (or MethodByName) or reflect.Type.Method (or MethodByName)

In the first case, the invoked method is marked as reachable. In the second case, all reachable interface types are decomposed into method signatures. Each encountered method is compared with the interface method signatures, and if there is a match, it is marked as reachable. This method is conservative but simple and correct.

In the third case, the algorithm handles methods by looking for functions marked as REFLECTMETHOD by the compiler. The presence of REFLECTMETHOD on a function F means that F uses reflection for method lookup, but the compiler cannot determine the method name during static analysis. Therefore, all functions that call reflect.Value.Method or reflect.Type.Method are marked as REFLECTMETHOD. Functions that call reflect.Value.MethodByName or reflect.Type.MethodByName with non-constant arguments are also considered REFLECTMETHOD. If a REFLECTMETHOD is found, static analysis is abandoned, and all exported methods of reachable types are marked as reachable.

Here is an example from the reference material:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// dead-code-elimination/demo3/main.go

type X struct{}
type Y struct{}

func (*X) One() { fmt.Println("hello 1") }
func (*X) Two() { fmt.Println("hello 2") }
func (*X) Three() { fmt.Println("hello 3") }
func (*Y) Four() { fmt.Println("hello 4") }
func (*Y) Five() { fmt.Println("hello 5") }

func main() {
var name string
fmt.Scanf("%s", &name)
reflect.ValueOf(&X{}).MethodByName(name).Call(nil)
var y Y
y.Five()
}

In this example, type *X has three methods, and type *Y has two methods. In the main function, we call the methods of an X instance through reflection and directly call a method of a Y instance. Let’s see which methods of X and Y are included in the final executable:

1
2
3
4
5
6
7
8
9
10
$ go build -gcflags='-l -N'

$ go tool nm ./demo | grep main
11d59c0 D go:main.inittasks
10d4500 T main.(*X).One
10d4640 T main.(*X).Three
10d45a0 T main.(*X).Two
10d46e0 T main.(*Y).Five
10d4780 T main.main
... ...

We can observe that only the directly called method Five of the reachable type Y is included in the final executable, while all methods of the reachable type X through reflection are present! This aligns with the third case mentioned earlier.

3. Summary

This article introduced the dead code elimination and executable file size reduction mechanisms in the Go language. Through experiments, we verified that only the functions called on the program execution path are included in the final executable, and unused functions are eliminated.

The article explained the Go build process, including package dependency graph calculation, compilation, and linking steps, and highlighted dead code elimination as an important optimization strategy. The specific dead code elimination algorithm is implemented through graph traversal, where reachable symbols are marked and unmarked symbols are considered unused. The article also mentioned the handling of type methods.

With this dead code elimination mechanism, Go controls the size of the final executable file, achieving executable file size reduction.

The source code mentioned in this article can be downloaded here.

4. References