prog: remove StructDesc

Remove StructDesc, KeyedStruct, StructKey and all associated
logic/complexity in prog and pkg/compiler.
We can now handle recursion more generically with the Ref type,
and Dir/FieldName are not a part of the type anymore.
This makes StructType/UnionType simpler and more natural.

Reduces size of sys/linux/gen/amd64.go from 5201321 to 4180861 (-20%).

Update #1580

4 files changed, 108 insertions, 202 deletions

diff --git a/pkg/compiler/compiler.go b/pkg/compiler/compiler.go
index f61d02036..55ddc1ba4 100644
--- a/pkg/compiler/compiler.go
+++ b/pkg/compiler/compiler.go
@@ -34,10 +34,9 @@ import (
 
 // Prog is description compilation result.
 type Prog struct {
-	Resources   []*prog.ResourceDesc
-	Syscalls    []*prog.Syscall
-	StructDescs []*prog.KeyedStruct
-	Types       []prog.Type
+	Resources []*prog.ResourceDesc
+	Syscalls  []*prog.Syscall
+	Types     []prog.Type
 	// Set of unsupported syscalls/flags.
 	Unsupported map[string]bool
 	// Returned if consts was nil.
@@ -61,9 +60,8 @@ func createCompiler(desc *ast.Description, target *targets.Target, eh ast.ErrorH
 		strFlags:     make(map[string]*ast.StrFlags),
 		used:         make(map[string]bool),
 		usedTypedefs: make(map[string]bool),
-		structDescs:  make(map[prog.StructKey]*prog.StructDesc),
-		structNodes:  make(map[*prog.StructDesc]*ast.Struct),
 		structVarlen: make(map[string]bool),
+		structTypes:  make(map[string]prog.Type),
 		builtinConsts: map[string]uint64{
 			"PTR_SIZE": target.PtrSize,
 		},
@@ -104,12 +102,11 @@ 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)
+	comp.layoutTypes(syscalls)
+	types := comp.generateTypes(syscalls)
 	prg := &Prog{
 		Resources:   comp.genResources(),
 		Syscalls:    syscalls,
-		StructDescs: structs,
 		Types:       types,
 		Unsupported: comp.unsupported,
 	}
@@ -139,9 +136,8 @@ type compiler struct {
 	used         map[string]bool // contains used structs/resources
 	usedTypedefs map[string]bool
 
-	structDescs   map[prog.StructKey]*prog.StructDesc
-	structNodes   map[*prog.StructDesc]*ast.Struct
 	structVarlen  map[string]bool
+	structTypes   map[string]prog.Type
 	builtinConsts map[string]uint64
 }
 
diff --git a/pkg/compiler/compiler_test.go b/pkg/compiler/compiler_test.go
index ae3b3d357..3d4ee3e64 100644
--- a/pkg/compiler/compiler_test.go
+++ b/pkg/compiler/compiler_test.go
@@ -122,8 +122,6 @@ func TestData(t *testing.T) {
 				out := new(bytes.Buffer)
 				fmt.Fprintf(out, "\n\nRESOURCES:\n")
 				serializer.Write(out, desc.Resources)
-				fmt.Fprintf(out, "\n\nSTRUCTS:\n")
-				serializer.Write(out, desc.StructDescs)
 				fmt.Fprintf(out, "\n\nSYSCALLS:\n")
 				serializer.Write(out, desc.Syscalls)
 				if false {
@@ -188,8 +186,6 @@ s2 {
 	if p == nil {
 		t.Fatal("failed to compile")
 	}
-	got := p.StructDescs[0].Desc
-	t.Logf("got: %#v", got)
 }
 
 func TestCollectUnusedError(t *testing.T) {
diff --git a/pkg/compiler/gen.go b/pkg/compiler/gen.go
index 748941bae..a86190863 100644
--- a/pkg/compiler/gen.go
+++ b/pkg/compiler/gen.go
@@ -138,26 +138,42 @@ func (comp *compiler) genSyscall(n *ast.Call, argSizes []uint64) *prog.Syscall {
 type typeProxy struct {
 	typ       prog.Type
 	id        string
+	ref       prog.Ref
 	locations []*prog.Type
 }
 
-func (comp *compiler) generateTypes(syscalls []*prog.Syscall, structs []*prog.KeyedStruct) []prog.Type {
+func (comp *compiler) generateTypes(syscalls []*prog.Syscall) []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].Type)
+	prog.ForeachTypePost(syscalls, func(typ prog.Type, ctx prog.TypeCtx) {
+		if _, ok := typ.(prog.Ref); ok {
+			return
 		}
-		if call.Ret != nil {
-			comp.collectTypes(proxies, &call.Ret)
+		if !typ.Varlen() && typ.Size() == sizeUnassigned {
+			panic("unassigned size")
 		}
-	}
-	for _, str := range structs {
-		for i := range str.Desc.Fields {
-			comp.collectTypes(proxies, &str.Desc.Fields[i].Type)
+		id := typ.Name()
+		switch typ.(type) {
+		case *prog.StructType, *prog.UnionType:
+			// There types can be uniquely identified with the name.
+		default:
+			buf := new(bytes.Buffer)
+			serializer.Write(buf, typ)
+			id = buf.String()
 		}
-	}
+		proxy := proxies[id]
+		if proxy == nil {
+			proxy = &typeProxy{
+				typ: typ,
+				id:  id,
+				ref: prog.Ref(len(proxies)),
+			}
+			proxies[id] = proxy
+		}
+		*ctx.Ptr = proxy.ref
+		proxy.locations = append(proxy.locations, ctx.Ptr)
+	})
 	array := make([]*typeProxy, 0, len(proxies))
 	for _, proxy := range proxies {
 		array = append(array, proxy)
@@ -175,142 +191,75 @@ func (comp *compiler) generateTypes(syscalls []*prog.Syscall, structs []*prog.Ke
 	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.Elem)
-	case *prog.ArrayType:
-		comp.collectTypes(proxies, &t.Elem)
-	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
-	// not possible to write them out inline as other types. To break the
-	// recursion detach them, and write StructDesc's out as separate array
-	// of KeyedStruct's. prog package will reattach them during init.
-	ctx := &structGen{
-		comp:   comp,
-		padded: make(map[interface{}]bool),
-		detach: make(map[**prog.StructDesc]bool),
-	}
-	// We have to do this in the loop until we pad nothing new
-	// due to recursive structs.
-	for {
-		start := len(ctx.padded)
-		for _, c := range syscalls {
-			for _, a := range c.Args {
-				ctx.walk(a.Type)
-			}
-			if c.Ret != nil {
-				ctx.walk(c.Ret)
-			}
-		}
-		if start == len(ctx.padded) {
-			break
-		}
-	}
-
-	// Detach StructDesc's from StructType's. prog will reattach them again.
-	for descp := range ctx.detach {
-		*descp = nil
-	}
-
-	sort.Slice(ctx.structs, func(i, j int) bool {
-		si, sj := ctx.structs[i].Key, ctx.structs[j].Key
-		return si.Name < sj.Name
+func (comp *compiler) layoutTypes(syscalls []*prog.Syscall) {
+	// Calculate struct/union/array sizes, add padding to structs, mark bitfields.
+	padded := make(map[prog.Type]bool)
+	prog.ForeachTypePost(syscalls, func(typ prog.Type, _ prog.TypeCtx) {
+		comp.layoutType(typ, padded)
 	})
-	return ctx.structs
-}
-
-type structGen struct {
-	comp    *compiler
-	padded  map[interface{}]bool
-	detach  map[**prog.StructDesc]bool
-	structs []*prog.KeyedStruct
 }
 
-func (ctx *structGen) check(key prog.StructKey, descp **prog.StructDesc) bool {
-	ctx.detach[descp] = true
-	desc := *descp
-	if ctx.padded[desc] {
-		return false
-	}
-	ctx.padded[desc] = true
-	for _, f := range desc.Fields {
-		ctx.walk(f.Type)
-		if !f.Varlen() && f.Size() == sizeUnassigned {
-			// An inner struct is not padded yet.
-			// Leave this struct for next iteration.
-			delete(ctx.padded, desc)
-			return false
-		}
-	}
-	if ctx.comp.used[key.Name] {
-		ctx.structs = append(ctx.structs, &prog.KeyedStruct{
-			Key:  key,
-			Desc: desc,
-		})
+func (comp *compiler) layoutType(typ prog.Type, padded map[prog.Type]bool) {
+	if padded[typ] {
+		return
 	}
-	return true
-}
-
-func (ctx *structGen) walk(t0 prog.Type) {
-	switch t := t0.(type) {
-	case *prog.PtrType:
-		ctx.walk(t.Elem)
+	switch t := typ.(type) {
 	case *prog.ArrayType:
-		ctx.walkArray(t)
+		comp.layoutType(t.Elem, padded)
+		comp.layoutArray(t)
 	case *prog.StructType:
-		ctx.walkStruct(t)
+		for _, f := range t.Fields {
+			comp.layoutType(f.Type, padded)
+		}
+		comp.layoutStruct(t)
 	case *prog.UnionType:
-		ctx.walkUnion(t)
-	}
-}
-
-func (ctx *structGen) walkArray(t *prog.ArrayType) {
-	if ctx.padded[t] {
+		for _, f := range t.Fields {
+			comp.layoutType(f.Type, padded)
+		}
+		comp.layoutUnion(t)
+	default:
 		return
 	}
-	ctx.walk(t.Elem)
-	if !t.Elem.Varlen() && t.Elem.Size() == sizeUnassigned {
-		// An inner struct is not padded yet.
-		// Leave this array for next iteration.
-		return
+	if !typ.Varlen() && typ.Size() == sizeUnassigned {
+		panic("size unassigned")
 	}
-	ctx.padded[t] = true
+	padded[typ] = true
+}
+
+func (comp *compiler) layoutArray(t *prog.ArrayType) {
 	t.TypeSize = 0
 	if t.Kind == prog.ArrayRangeLen && t.RangeBegin == t.RangeEnd && !t.Elem.Varlen() {
 		t.TypeSize = t.RangeBegin * t.Elem.Size()
 	}
 }
 
-func (ctx *structGen) walkStruct(t *prog.StructType) {
-	if !ctx.check(t.Key, &t.StructDesc) {
+func (comp *compiler) layoutUnion(t *prog.UnionType) {
+	structNode := comp.structs[t.TypeName]
+	attrs := comp.parseAttrs(unionAttrs, structNode, structNode.Attrs)
+	t.TypeSize = 0
+	if attrs[attrVarlen] != 0 {
 		return
 	}
-	comp := ctx.comp
-	structNode := comp.structNodes[t.StructDesc]
+	sizeAttr, hasSize := attrs[attrSize]
+	for i, fld := range t.Fields {
+		sz := fld.Size()
+		if hasSize && sz > sizeAttr {
+			comp.error(structNode.Fields[i].Pos, "union %v has size attribute %v"+
+				" which is less than field %v size %v",
+				structNode.Name.Name, sizeAttr, fld.Type.Name(), sz)
+		}
+		if t.TypeSize < sz {
+			t.TypeSize = sz
+		}
+	}
+	if hasSize {
+		t.TypeSize = sizeAttr
+	}
+}
+
+func (comp *compiler) layoutStruct(t *prog.StructType) {
 	// Add paddings, calculate size, mark bitfields.
+	structNode := comp.structs[t.TypeName]
 	varlen := false
 	for _, f := range t.Fields {
 		if f.Varlen() {
@@ -319,7 +268,7 @@ func (ctx *structGen) walkStruct(t *prog.StructType) {
 	}
 	attrs := comp.parseAttrs(structAttrs, structNode, structNode.Attrs)
 	t.AlignAttr = attrs[attrAlign]
-	comp.layoutStruct(t, varlen, attrs[attrPacked] != 0)
+	comp.layoutStructFields(t, varlen, attrs[attrPacked] != 0)
 	t.TypeSize = 0
 	if !varlen {
 		for _, f := range t.Fields {
@@ -340,46 +289,7 @@ func (ctx *structGen) walkStruct(t *prog.StructType) {
 	}
 }
 
-func (ctx *structGen) walkUnion(t *prog.UnionType) {
-	if !ctx.check(t.Key, &t.StructDesc) {
-		return
-	}
-	comp := ctx.comp
-	structNode := comp.structNodes[t.StructDesc]
-	attrs := comp.parseAttrs(unionAttrs, structNode, structNode.Attrs)
-	t.TypeSize = 0
-	if attrs[attrVarlen] != 0 {
-		return
-	}
-	sizeAttr, hasSize := attrs[attrSize]
-	for i, fld := range t.Fields {
-		sz := fld.Size()
-		if hasSize && sz > sizeAttr {
-			comp.error(structNode.Fields[i].Pos, "union %v has size attribute %v"+
-				" which is less than field %v size %v",
-				structNode.Name.Name, sizeAttr, fld.Type.Name(), sz)
-		}
-		if t.TypeSize < sz {
-			t.TypeSize = sz
-		}
-	}
-	if hasSize {
-		t.TypeSize = sizeAttr
-	}
-}
-
-func (comp *compiler) genStructDesc(res *prog.StructDesc, n *ast.Struct, varlen bool) {
-	// Leave node for genStructDescs to calculate size/padding.
-	comp.structNodes[res] = n
-	common := genCommon(n.Name.Name, sizeUnassigned, false)
-	common.IsVarlen = varlen
-	*res = prog.StructDesc{
-		TypeCommon: common,
-		Fields:     comp.genFieldArray(n.Fields, make([]uint64, len(n.Fields))),
-	}
-}
-
-func (comp *compiler) layoutStruct(t *prog.StructType, varlen, packed bool) {
+func (comp *compiler) layoutStructFields(t *prog.StructType, varlen, packed bool) {
 	var newFields []prog.Field
 	var structAlign, byteOffset, bitOffset uint64
 	for i, field := range t.Fields {
@@ -538,7 +448,7 @@ func (comp *compiler) typeAlign(t0 prog.Type) uint64 {
 	case *prog.ArrayType:
 		return comp.typeAlign(t.Elem)
 	case *prog.StructType:
-		n := comp.structNodes[t.StructDesc]
+		n := comp.structs[t.TypeName]
 		attrs := comp.parseAttrs(structAttrs, n, n.Attrs)
 		if align := attrs[attrAlign]; align != 0 {
 			return align // overrided by user attribute
diff --git a/pkg/compiler/types.go b/pkg/compiler/types.go
index 7ed12afd2..44ccb1f1d 100644
--- a/pkg/compiler/types.go
+++ b/pkg/compiler/types.go
@@ -237,7 +237,7 @@ var typeArray = &typeDesc{
 				RangeEnd:   end,
 			}
 		}
-		// TypeSize is assigned later in genStructDescs.
+		// TypeSize is assigned later in layoutArray.
 		return &prog.ArrayType{
 			TypeCommon: base.TypeCommon,
 			Elem:       elemType,
@@ -815,27 +815,31 @@ func init() {
 		return true
 	}
 	typeStruct.Gen = func(comp *compiler, t *ast.Type, args []*ast.Type, base prog.IntTypeCommon) prog.Type {
-		s := comp.structs[t.Ident]
-		key := prog.StructKey{
-			Name: t.Ident,
-		}
-		desc := comp.structDescs[key]
-		if desc == nil {
-			// Need to assign to structDescs before calling genStructDesc to break recursion.
-			desc = new(prog.StructDesc)
-			comp.structDescs[key] = desc
-			comp.genStructDesc(desc, s, typeStruct.Varlen(comp, t, args))
+		if typ := comp.structTypes[t.Ident]; typ != nil {
+			return typ
 		}
+		s := comp.structs[t.Ident]
+		common := genCommon(t.Ident, sizeUnassigned, false)
+		common.IsVarlen = typeStruct.Varlen(comp, t, args)
+		var typ prog.Type
 		if s.IsUnion {
-			return &prog.UnionType{
-				Key:        key,
-				StructDesc: desc,
+			typ = &prog.UnionType{
+				TypeCommon: common,
+			}
+		} else {
+			typ = &prog.StructType{
+				TypeCommon: common,
 			}
 		}
-		return &prog.StructType{
-			Key:        key,
-			StructDesc: desc,
+		// Need to cache type in structTypes before generating fields to break recursion.
+		comp.structTypes[t.Ident] = typ
+		fields := comp.genFieldArray(s.Fields, make([]uint64, len(s.Fields)))
+		if s.IsUnion {
+			typ.(*prog.UnionType).Fields = fields
+		} else {
+			typ.(*prog.StructType).Fields = fields
 		}
+		return typ
 	}
 }