From 58ae5e18624eaaac79cab00e63d6f32c9bd64ee0 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Sun, 3 May 2020 11:29:12 +0200 Subject: 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 --- pkg/compiler/compiler.go | 18 ++- pkg/compiler/compiler_test.go | 4 - pkg/compiler/gen.go | 250 ++++++++++++++---------------------------- pkg/compiler/types.go | 38 ++++--- 4 files changed, 108 insertions(+), 202 deletions(-) (limited to 'pkg/compiler') 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 } } -- cgit mrf-deployment