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

1 files changed, 26 insertions, 4 deletions

diff --git a/prog/target.go b/prog/target.go
index 5c97b5e50..f9e10b6f4 100644
--- a/prog/target.go
+++ b/prog/target.go
@@ -24,6 +24,7 @@ type Target struct {
 	Resources []*ResourceDesc
 	Structs   []*KeyedStruct
 	Consts    []ConstValue
+	Types     []Type
 
 	// MakeDataMmap creates calls that mmaps target data memory range.
 	MakeDataMmap func() []*Call
@@ -136,8 +137,9 @@ func (target *Target) initTarget() {
 		target.ConstMap[c.Name] = c.Value
 	}
 
-	target.resourceMap = restoreLinks(target.Syscalls, target.Resources, target.Structs)
+	target.resourceMap = restoreLinks(target.Syscalls, target.Resources, target.Structs, target.Types)
 	target.Structs = nil
+	target.Types = nil
 
 	target.SyscallMap = make(map[string]*Syscall)
 	for i, c := range target.Syscalls {
@@ -171,11 +173,12 @@ func (target *Target) sanitize(c *Call, fix bool) error {
 	return nil
 }
 
-func RestoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct) {
-	restoreLinks(syscalls, resources, structs)
+func RestoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct, types []Type) {
+	restoreLinks(syscalls, resources, structs, types)
 }
 
-func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct) map[string]*ResourceDesc {
+func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct,
+	types []Type) map[string]*ResourceDesc {
 	resourceMap := make(map[string]*ResourceDesc)
 	for _, res := range resources {
 		resourceMap[res.Name] = res
@@ -183,10 +186,23 @@ func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*Key
 	keyedStructs := make(map[StructKey]*StructDesc)
 	for _, desc := range structs {
 		keyedStructs[desc.Key] = desc.Desc
+		for i := range desc.Desc.Fields {
+			unref(&desc.Desc.Fields[i], types)
+		}
 	}
 	for _, c := range syscalls {
+		for i := range c.Args {
+			unref(&c.Args[i], types)
+		}
+		if c.Ret != nil {
+			unref(&c.Ret, types)
+		}
 		ForeachType(c, func(t0 Type) {
 			switch t := t0.(type) {
+			case *PtrType:
+				unref(&t.Type, types)
+			case *ArrayType:
+				unref(&t.Type, types)
 			case *ResourceType:
 				t.Desc = resourceMap[t.TypeName]
 				if t.Desc == nil {
@@ -208,6 +224,12 @@ func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*Key
 	return resourceMap
 }
 
+func unref(tp *Type, types []Type) {
+	if ref, ok := (*tp).(Ref); ok {
+		*tp = types[ref]
+	}
+}
+
 type Gen struct {
 	r *randGen
 	s *state