pkg/compiler: deduplicate Types in descriptions

Add prog.Ref Type that serves as a proxy for real types
and allows to deduplicate Types in generated descriptions.
The Ref type is effectively an index in an array of types.
Just before serialization pkg/compiler replaces real types
with the Ref types and prepares corresponding array of real types.
When a Target is registered in prog package, we do the opposite
operation and replace Ref's with the corresponding real types.

This brings improvements across the board:
compiler memory consumption is reduced by 15%,
test building time by 25%, descriptions size by 33%.

Before:
$ du -h sys/linux/gen
54M	sys/linux/gen

$ time GOMAXPROCS=1 go test -p=1 -c ./prog
real	0m54.200s
real	0m53.883s

$ time GOMAXPROCS=1 go install -p=1 ./tools/syz-execprog
real	0m27.911s
real	0m27.767s

$ TIME="%e %P %M" GOMAXPROCS=1 time go tool compile ./sys/linux/gen
20.59 100% 3200016
20.97 100% 3445976
20.25 100% 3209684

After:
$ du -h sys/linux/gen
36M	sys/linux/gen

$ time GOMAXPROCS=1 go test -p=1 -c ./prog
real	0m42.290s
real	0m43.230s

$ time GOMAXPROCS=1 go install -p=1 ./tools/syz-execprog
real	0m24.337s
real	0m24.727s

$ TIME="%e %P %M" GOMAXPROCS=1 time go tool compile ./sys/linux/gen
19.11 100% 2764952
19.66 100% 2787624
19.35 100% 2749376

Update #1580

2 files changed, 74 insertions, 1 deletions

diff --git a/pkg/compiler/compiler.go b/pkg/compiler/compiler.go
index a9146305b..7316b4d4c 100644
--- a/pkg/compiler/compiler.go
+++ b/pkg/compiler/compiler.go
@@ -37,6 +37,7 @@ type Prog struct {
 	Resources   []*prog.ResourceDesc
 	Syscalls    []*prog.Syscall
 	StructDescs []*prog.KeyedStruct
+	Types       []prog.Type
 	// Set of unsupported syscalls/flags.
 	Unsupported map[string]bool
 	// Returned if consts was nil.
@@ -103,10 +104,13 @@ func Compile(desc *ast.Description, consts map[string]uint64, target *targets.Ta
 		return nil
 	}
 	syscalls := comp.genSyscalls()
+	structs := comp.genStructDescs(syscalls)
+	types := comp.generateTypes(syscalls, structs)
 	prg := &Prog{
 		Resources:   comp.genResources(),
 		Syscalls:    syscalls,
-		StructDescs: comp.genStructDescs(syscalls),
+		StructDescs: structs,
+		Types:       types,
 		Unsupported: comp.unsupported,
 	}
 	if comp.errors != 0 {
diff --git a/pkg/compiler/gen.go b/pkg/compiler/gen.go
index 4b1b05ed1..c8255c554 100644
--- a/pkg/compiler/gen.go
+++ b/pkg/compiler/gen.go
@@ -4,11 +4,13 @@
 package compiler
 
 import (
+	"bytes"
 	"fmt"
 	"reflect"
 	"sort"
 
 	"github.com/google/syzkaller/pkg/ast"
+	"github.com/google/syzkaller/pkg/serializer"
 	"github.com/google/syzkaller/prog"
 )
 
@@ -133,6 +135,73 @@ func (comp *compiler) genSyscall(n *ast.Call, argSizes []uint64) *prog.Syscall {
 	}
 }
 
+type typeProxy struct {
+	typ       prog.Type
+	id        string
+	locations []*prog.Type
+}
+
+func (comp *compiler) generateTypes(syscalls []*prog.Syscall, structs []*prog.KeyedStruct) []prog.Type {
+	// Replace all Type's in the descriptions with Ref's
+	// and prepare a sorted array of corresponding real types.
+	proxies := make(map[string]*typeProxy)
+	for _, call := range syscalls {
+		for i := range call.Args {
+			comp.collectTypes(proxies, &call.Args[i])
+		}
+		if call.Ret != nil {
+			comp.collectTypes(proxies, &call.Ret)
+		}
+	}
+	for _, str := range structs {
+		for i := range str.Desc.Fields {
+			comp.collectTypes(proxies, &str.Desc.Fields[i])
+		}
+	}
+	array := make([]*typeProxy, 0, len(proxies))
+	for _, proxy := range proxies {
+		array = append(array, proxy)
+	}
+	sort.Slice(array, func(i, j int) bool {
+		return array[i].id < array[j].id
+	})
+	types := make([]prog.Type, len(array))
+	for i, proxy := range array {
+		types[i] = proxy.typ
+		for _, loc := range proxy.locations {
+			*loc = prog.Ref(i)
+		}
+	}
+	return types
+}
+
+func (comp *compiler) collectTypes(proxies map[string]*typeProxy, tptr *prog.Type) {
+	typ := *tptr
+	switch t := typ.(type) {
+	case *prog.PtrType:
+		comp.collectTypes(proxies, &t.Type)
+	case *prog.ArrayType:
+		comp.collectTypes(proxies, &t.Type)
+	case *prog.ResourceType, *prog.BufferType, *prog.VmaType, *prog.LenType,
+		*prog.FlagsType, *prog.ConstType, *prog.IntType, *prog.ProcType,
+		*prog.CsumType, *prog.StructType, *prog.UnionType:
+	default:
+		panic("unknown type")
+	}
+	buf := new(bytes.Buffer)
+	serializer.Write(buf, typ)
+	id := buf.String()
+	proxy := proxies[id]
+	if proxy == nil {
+		proxy = &typeProxy{
+			typ: typ,
+			id:  id,
+		}
+		proxies[id] = proxy
+	}
+	proxy.locations = append(proxy.locations, tptr)
+}
+
 func (comp *compiler) genStructDescs(syscalls []*prog.Syscall) []*prog.KeyedStruct {
 	// Calculate struct/union/array sizes, add padding to structs and detach
 	// StructDesc's from StructType's. StructType's can be recursive so it's