[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 <mdempsky@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>

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