From 5517053d178d1259f6f1a9c2d65efbf335002cea Mon Sep 17 00:00:00 2001 From: Matthew Dempsky Date: Tue, 13 Jul 2021 09:09:32 -0700 Subject: [PATCH] [dev.typeparams] cmd/compile: record more typ/fun info for dictionaries in unified IR Records whether a derived type is needed at run-time as well as instantiated functions that rely on derived types (and thus need sub-dictionaries). Change-Id: I2f2036976bfce5b3b4372fba88b4116dafa7e6b7 Reviewed-on: https://go-review.googlesource.com/c/go/+/334349 Trust: Matthew Dempsky Run-TryBot: Matthew Dempsky TryBot-Result: Go Bot Reviewed-by: Cuong Manh Le --- src/cmd/compile/internal/noder/reader.go | 57 +++++++-- src/cmd/compile/internal/noder/reader2.go | 50 ++++---- src/cmd/compile/internal/noder/unified.go | 3 + src/cmd/compile/internal/noder/writer.go | 139 ++++++++++++++++++---- 4 files changed, 188 insertions(+), 61 deletions(-) diff --git a/src/cmd/compile/internal/noder/reader.go b/src/cmd/compile/internal/noder/reader.go index 2351d1d0ba..de708769ba 100644 --- a/src/cmd/compile/internal/noder/reader.go +++ b/src/cmd/compile/internal/noder/reader.go @@ -142,8 +142,11 @@ type readerDict struct { // arguments; the rest are explicit. implicits int - derivedReloc []int // reloc index of the derived type's descriptor - derived []*types.Type // slice of previously computed derived types + derived []derivedInfo // reloc index of the derived type's descriptor + derivedTypes []*types.Type // slice of previously computed derived types + + funcs []objInfo + funcsObj []ir.Node } func (r *reader) setType(n ir.Node, typ *types.Type) { @@ -293,18 +296,23 @@ func (r *reader) doPkg() *types.Pkg { // @@@ Types func (r *reader) typ() *types.Type { + return r.p.typIdx(r.typInfo(), r.dict) +} + +func (r *reader) typInfo() typeInfo { r.sync(syncType) if r.bool() { - return r.p.typIdx(r.len(), r.dict) + return typeInfo{idx: r.len(), derived: true} } - return r.p.typIdx(r.reloc(relocType), nil) + return typeInfo{idx: r.reloc(relocType), derived: false} } -func (pr *pkgReader) typIdx(idx int, dict *readerDict) *types.Type { +func (pr *pkgReader) typIdx(info typeInfo, dict *readerDict) *types.Type { + idx := info.idx var where **types.Type - if dict != nil { - where = &dict.derived[idx] - idx = dict.derivedReloc[idx] + if info.derived { + where = &dict.derivedTypes[idx] + idx = dict.derived[idx].idx } else { where = &pr.typs[idx] } @@ -493,6 +501,23 @@ var objReader = map[*types.Sym]pkgReaderIndex{} func (r *reader) obj() ir.Node { r.sync(syncObject) + if r.bool() { + idx := r.len() + obj := r.dict.funcsObj[idx] + if obj == nil { + fn := r.dict.funcs[idx] + targs := make([]*types.Type, len(fn.explicits)) + for i, targ := range fn.explicits { + targs[i] = r.p.typIdx(targ, r.dict) + } + + obj = r.p.objIdx(fn.idx, nil, targs) + assert(r.dict.funcsObj[idx] == nil) + r.dict.funcsObj[idx] = obj + } + return obj + } + idx := r.reloc(relocObj) explicits := make([]*types.Type, r.len()) @@ -539,10 +564,20 @@ func (pr *pkgReader) objIdx(idx int, implicits, explicits []*types.Type) ir.Node { rdict := pr.newReader(relocObjDict, idx, syncObject1) - r.dict.derivedReloc = make([]int, rdict.len()) - r.dict.derived = make([]*types.Type, len(r.dict.derivedReloc)) + r.dict.derived = make([]derivedInfo, rdict.len()) + r.dict.derivedTypes = make([]*types.Type, len(r.dict.derived)) for i := range r.dict.derived { - r.dict.derivedReloc[i] = rdict.reloc(relocType) + r.dict.derived[i] = derivedInfo{rdict.reloc(relocType), rdict.bool()} + } + r.dict.funcs = make([]objInfo, rdict.len()) + r.dict.funcsObj = make([]ir.Node, len(r.dict.funcs)) + for i := range r.dict.funcs { + objIdx := rdict.reloc(relocObj) + targs := make([]typeInfo, rdict.len()) + for j := range targs { + targs[j] = rdict.typInfo() + } + r.dict.funcs[i] = objInfo{idx: objIdx, explicits: targs} } } diff --git a/src/cmd/compile/internal/noder/reader2.go b/src/cmd/compile/internal/noder/reader2.go index ac29f6f519..a2339145fa 100644 --- a/src/cmd/compile/internal/noder/reader2.go +++ b/src/cmd/compile/internal/noder/reader2.go @@ -61,12 +61,12 @@ type reader2 struct { } type reader2Dict struct { - bounds []reader2TypeBound + bounds []typeInfo tparams []*types2.TypeParam - derivedReloc []int - derived []types2.Type + derived []derivedInfo + derivedTypes []types2.Type } type reader2TypeBound struct { @@ -176,18 +176,23 @@ func (r *reader2) doPkg() *types2.Package { // @@@ Types func (r *reader2) typ() types2.Type { + return r.p.typIdx(r.typInfo(), r.dict) +} + +func (r *reader2) typInfo() typeInfo { r.sync(syncType) if r.bool() { - return r.p.typIdx(r.len(), r.dict) + return typeInfo{idx: r.len(), derived: true} } - return r.p.typIdx(r.reloc(relocType), nil) + return typeInfo{idx: r.reloc(relocType), derived: false} } -func (pr *pkgReader2) typIdx(idx int, dict *reader2Dict) types2.Type { +func (pr *pkgReader2) typIdx(info typeInfo, dict *reader2Dict) types2.Type { + idx := info.idx var where *types2.Type - if dict != nil { - where = &dict.derived[idx] - idx = dict.derivedReloc[idx] + if info.derived { + where = &dict.derivedTypes[idx] + idx = dict.derived[idx].idx } else { where = &pr.typs[idx] } @@ -339,6 +344,8 @@ func (r *reader2) param() *types2.Var { func (r *reader2) obj() (types2.Object, []types2.Type) { r.sync(syncObject) + assert(!r.bool()) + pkg, name := r.p.objIdx(r.reloc(relocObj)) obj := pkg.Scope().Lookup(name) @@ -367,11 +374,12 @@ func (pr *pkgReader2) objIdx(idx int) (*types2.Package, string) { { rdict := r.p.newReader(relocObjDict, idx, syncObject1) - r.dict.derivedReloc = make([]int, rdict.len()) - r.dict.derived = make([]types2.Type, len(r.dict.derivedReloc)) + r.dict.derived = make([]derivedInfo, rdict.len()) + r.dict.derivedTypes = make([]types2.Type, len(r.dict.derived)) for i := range r.dict.derived { - r.dict.derivedReloc[i] = rdict.reloc(relocType) + r.dict.derived[i] = derivedInfo{rdict.reloc(relocType), rdict.bool()} } + // function references follow, but reader2 doesn't need those } objPkg.Scope().InsertLazy(objName, func() types2.Object { @@ -438,16 +446,9 @@ func (r *reader2) typeParamBounds() { base.Fatalf("unexpected object with %v implicit type parameter(s)", implicits) } - r.dict.bounds = make([]reader2TypeBound, r.len()) + r.dict.bounds = make([]typeInfo, r.len()) for i := range r.dict.bounds { - b := &r.dict.bounds[i] - r.sync(syncType) - b.derived = r.bool() - if b.derived { - b.boundIdx = r.len() - } else { - b.boundIdx = r.reloc(relocType) - } + r.dict.bounds[i] = r.typInfo() } } @@ -479,12 +480,7 @@ func (r *reader2) typeParamNames() []*types2.TypeName { } for i, bound := range r.dict.bounds { - var dict *reader2Dict - if bound.derived { - dict = r.dict - } - boundType := r.p.typIdx(bound.boundIdx, dict) - r.dict.tparams[i].SetBound(boundType) + r.dict.tparams[i].SetBound(r.p.typIdx(bound, r.dict)) } return names diff --git a/src/cmd/compile/internal/noder/unified.go b/src/cmd/compile/internal/noder/unified.go index 39989778f8..e8c203ae46 100644 --- a/src/cmd/compile/internal/noder/unified.go +++ b/src/cmd/compile/internal/noder/unified.go @@ -259,6 +259,7 @@ func readPackage(pr *pkgReader, importpkg *types.Pkg) { for i, n := 0, r.len(); i < n; i++ { r.sync(syncObject) + assert(!r.bool()) idx := r.reloc(relocObj) assert(r.len() == 0) @@ -293,6 +294,7 @@ func writeNewExport(out io.Writer) { for i, n := 0, r.len(); i < n; i++ { r.sync(syncObject) + assert(!r.bool()) idx := r.reloc(relocObj) assert(r.len() == 0) @@ -325,6 +327,7 @@ func writeNewExport(out io.Writer) { w.len(len(idxs)) for _, idx := range idxs { w.sync(syncObject) + w.bool(false) w.reloc(relocObj, idx) w.len(0) } diff --git a/src/cmd/compile/internal/noder/writer.go b/src/cmd/compile/internal/noder/writer.go index 21aeb5678d..48884056f3 100644 --- a/src/cmd/compile/internal/noder/writer.go +++ b/src/cmd/compile/internal/noder/writer.go @@ -103,11 +103,53 @@ type writerDict struct { // derived is a slice of type indices for computing derived types // (i.e., types that depend on the declaration's type parameters). - derived []int + derived []derivedInfo // derivedIdx maps a Type to its corresponding index within the // derived slice, if present. derivedIdx map[types2.Type]int + + // funcs lists references to generic functions that were + // instantiated with derived types (i.e., that require + // sub-dictionaries when called at run time). + funcs []objInfo +} + +type derivedInfo struct { + idx int + needed bool +} + +type typeInfo struct { + idx int + derived bool +} + +type objInfo struct { + idx int // index for the generic function declaration + explicits []typeInfo // info for the type arguments +} + +func (info objInfo) anyDerived() bool { + for _, explicit := range info.explicits { + if explicit.derived { + return true + } + } + return false +} + +func (info objInfo) equals(other objInfo) bool { + if info.idx != other.idx { + return false + } + assert(len(info.explicits) == len(other.explicits)) + for i, targ := range info.explicits { + if targ != other.explicits[i] { + return false + } + } + return true } func (pw *pkgWriter) newWriter(k reloc, marker syncMarker) *writer { @@ -200,14 +242,16 @@ func (pw *pkgWriter) pkgIdx(pkg *types2.Package) int { // @@@ Types func (w *writer) typ(typ types2.Type) { - idx, derived := w.p.typIdx(typ, w.dict) + w.typInfo(w.p.typIdx(typ, w.dict)) +} +func (w *writer) typInfo(info typeInfo) { w.sync(syncType) - if w.bool(derived) { - w.len(idx) + if w.bool(info.derived) { + w.len(info.idx) w.derived = true } else { - w.reloc(relocType, idx) + w.reloc(relocType, info.idx) } } @@ -216,17 +260,17 @@ func (w *writer) typ(typ types2.Type) { // // typIdx also reports whether typ is a derived type; that is, whether // its identity depends on type parameters. -func (pw *pkgWriter) typIdx(typ types2.Type, dict *writerDict) (int, bool) { +func (pw *pkgWriter) typIdx(typ types2.Type, dict *writerDict) typeInfo { if quirksMode() { typ = pw.dups.orig(typ) } if idx, ok := pw.typsIdx[typ]; ok { - return idx, false + return typeInfo{idx: idx, derived: false} } if dict != nil { if idx, ok := dict.derivedIdx[typ]; ok { - return idx, true + return typeInfo{idx: idx, derived: true} } } @@ -324,13 +368,13 @@ func (pw *pkgWriter) typIdx(typ types2.Type, dict *writerDict) (int, bool) { if w.derived { idx := len(dict.derived) - dict.derived = append(dict.derived, w.flush()) + dict.derived = append(dict.derived, derivedInfo{idx: w.flush()}) dict.derivedIdx[typ] = idx - return idx, true + return typeInfo{idx: idx, derived: true} } pw.typsIdx[typ] = w.idx - return w.flush(), false + return typeInfo{idx: w.flush(), derived: false} } func (w *writer) structType(typ *types2.Struct) { @@ -398,6 +442,34 @@ func (w *writer) param(param *types2.Var) { // @@@ Objects func (w *writer) obj(obj types2.Object, explicits []types2.Type) { + explicitInfos := make([]typeInfo, len(explicits)) + for i, explicit := range explicits { + explicitInfos[i] = w.p.typIdx(explicit, w.dict) + } + info := objInfo{idx: w.p.objIdx(obj), explicits: explicitInfos} + + if _, ok := obj.(*types2.Func); ok && info.anyDerived() { + idx := -1 + for i, prev := range w.dict.funcs { + if prev.equals(info) { + idx = i + } + } + if idx < 0 { + idx = len(w.dict.funcs) + w.dict.funcs = append(w.dict.funcs, info) + } + + // TODO(mdempsky): Push up into expr; this shouldn't appear + // outside of expression context. + w.sync(syncObject) + w.bool(true) + w.len(idx) + return + } + + // TODO(mdempsky): Push up into typIdx; this shouldn't be needed + // except while writing out types. if isDefinedType(obj) && obj.Pkg() == w.p.curpkg { decl, ok := w.p.typDecls[obj.(*types2.TypeName)] assert(ok) @@ -407,11 +479,12 @@ func (w *writer) obj(obj types2.Object, explicits []types2.Type) { } w.sync(syncObject) - w.reloc(relocObj, w.p.objIdx(obj)) + w.bool(false) + w.reloc(relocObj, info.idx) - w.len(len(explicits)) - for _, explicit := range explicits { - w.typ(explicit) + w.len(len(info.explicits)) + for _, info := range info.explicits { + w.typInfo(info) } } @@ -453,16 +526,19 @@ func (pw *pkgWriter) objIdx(obj types2.Object) int { w.ext.flush() // Done writing out the object description; write out the list of - // derived types that we found along the way. - // - // TODO(mdempsky): Record details about how derived types are - // actually used so reader can optimize its runtime dictionaries. - // - // TODO(mdempsky): Record details about which instantiated functions - // are used too. + // derived types and instantiated functions found along the way. wdict.len(len(dict.derived)) for _, typ := range dict.derived { - wdict.reloc(relocType, typ) + wdict.reloc(relocType, typ.idx) + wdict.bool(typ.needed) + } + wdict.len(len(dict.funcs)) + for _, fn := range dict.funcs { + wdict.reloc(relocObj, fn.idx) + wdict.len(len(fn.explicits)) + for _, targ := range fn.explicits { + wdict.typInfo(targ) + } } wdict.flush() @@ -1103,6 +1179,9 @@ func (w *writer) expr(expr syntax.Expr) { obj, targs := lookupObj(w.p.info, expr) if tv, ok := w.p.info.Types[expr]; ok { + // TODO(mdempsky): Be more judicious about which types are marked as "needed". + w.needType(tv.Type) + if tv.IsType() { w.code(exprType) w.typ(tv.Type) @@ -1356,6 +1435,20 @@ func (w *writer) op(op ir.Op) { w.len(int(op)) } +func (w *writer) needType(typ types2.Type) { + // Decompose tuple into component element types. + if typ, ok := typ.(*types2.Tuple); ok { + for i := 0; i < typ.Len(); i++ { + w.needType(typ.At(i).Type()) + } + return + } + + if info := w.p.typIdx(typ, w.dict); info.derived { + w.dict.derived[info.idx].needed = true + } +} + // @@@ Package initialization // Caution: This code is still clumsy, because toolstash -cmp is -- 2.48.1