go/types, types2: make each method instantiation independently lazy

Method signatures can introduce a significant number of edges into the
type graph. One can imagine a generic type with many methods, each of
which may use other instantiated types, etc. For performance, when type
checking generic code, we should avoid unnecessary instantiation of
methods wherever possible.

This CL achieves this by making method instantiation lazy at the
individual method level. It abstracts method access into a methodList
type, which may be either eager or lazy. In the lazy case, methods are
only instantiated when they are accessed via the Named.Method,
MethodSet, or LookupFieldOrMethod APIs. Factoring out a methodList type
makes it easier to verify that we're not leaking the methods slice
anywhere, and as a side benefit reduces the size of *Named types in the
case where there are no methods. The effective memory footprint of Named
types with methods increases by a pointer (to hold the slice of guards),
and the footprint of instantiated named types increases additionally by
a sync.Once per method. We estimate that this memory increase is more
than offset by the reduction in the number of instantiated methods.

This also simplifies the code. Previously we had to work around the fact
that named type expansion could occur before all signatures were set-up,
by stashing the instantiated receiver into a partially filled-out *Func.
With fully lazy methods, we can rely on the invariant that any use of
methods in valid code can only occur after all signatures can be type
checked. This means that we can fully instantiate the *Func, and don't
need to deal with partially instantiated stubs.

Finally, this CL fixes a bug (issue #50619), where traversing
Method->Receiver Type->Method did not get us back where we started. This
is fixed by not instantiating a new method if t is already the receiver
base of the original method.

A test is added to explicitly verify the invariant above, and more test
cases are added for the behavior of Info with respect to generic code.

Fixes #50619

Change-Id: I5b6d2bdc4404c9f5dcb583a29cb64e8af9794c54
Reviewed-on: https://go-review.googlesource.com/c/go/+/380499
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>

21 files changed, 698 insertions, 206 deletions

diff --git a/src/cmd/compile/internal/types2/api_test.go b/src/cmd/compile/internal/types2/api_test.go
index 3b75818d56..b54f84dde0 100644
--- a/src/cmd/compile/internal/types2/api_test.go
+++ b/src/cmd/compile/internal/types2/api_test.go
@@ -640,6 +640,11 @@ func TestDefsInfo(t *testing.T) {
 		{`package p3; type x int`, `x`, `type p3.x int`},
 		{`package p4; func f()`, `f`, `func p4.f()`},
 		{`package p5; func f() int { x, _ := 1, 2; return x }`, `_`, `var _ int`},
+
+		// Tests using generics.
+		{`package g0; type x[T any] int`, `x`, `type g0.x[T any] int`},
+		{`package g1; func f[T any]() {}`, `f`, `func g1.f[T any]()`},
+		{`package g2; type x[T any] int; func (*x[_]) m() {}`, `m`, `func (*g2.x[_]).m()`},
 	}
 
 	for _, test := range tests {
@@ -678,6 +683,20 @@ func TestUsesInfo(t *testing.T) {
 		{`package p2; func _() { _ = x }; var x int`, `x`, `var p2.x int`},
 		{`package p3; func _() { type _ x }; type x int`, `x`, `type p3.x int`},
 		{`package p4; func _() { _ = f }; func f()`, `f`, `func p4.f()`},
+
+		// Tests using generics.
+		{`package g0; func _[T any]() { _ = x }; const x = 42`, `x`, `const g0.x untyped int`},
+		{`package g1; func _[T any](x T) { }`, `T`, `type parameter T any`},
+		{`package g2; type N[A any] int; var _ N[int]`, `N`, `type g2.N[A any] int`},
+		{`package g3; type N[A any] int; func (N[_]) m() {}`, `N`, `type g3.N[A any] int`},
+
+		// Uses of fields are instantiated.
+		{`package s1; type N[A any] struct{ a A }; var f = N[int]{}.a`, `a`, `field a int`},
+		{`package s1; type N[A any] struct{ a A }; func (r N[B]) m(b B) { r.a = b }`, `a`, `field a B`},
+
+		// Uses of methods are uses of the instantiated method.
+		{`package m0; type N[A any] int; func (r N[B]) m() { r.n() }; func (N[C]) n() {}`, `n`, `func (m0.N[B]).n()`},
+		{`package m1; type N[A any] int; func (r N[B]) m() { }; var f = N[int].m`, `m`, `func (m1.N[int]).m()`},
 	}
 
 	for _, test := range tests {
@@ -705,6 +724,89 @@ func TestUsesInfo(t *testing.T) {
 	}
 }
 
+func TestGenericMethodInfo(t *testing.T) {
+	src := `package p
+
+type N[A any] int
+
+func (r N[B]) m() { r.m(); r.n() }
+
+func (r *N[C]) n() {  }
+`
+	f, err := parseSrc("p.go", src)
+	if err != nil {
+		t.Fatal(err)
+	}
+	info := Info{
+		Defs:       make(map[*syntax.Name]Object),
+		Uses:       make(map[*syntax.Name]Object),
+		Selections: make(map[*syntax.SelectorExpr]*Selection),
+	}
+	var conf Config
+	pkg, err := conf.Check("p", []*syntax.File{f}, &info)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	N := pkg.Scope().Lookup("N").Type().(*Named)
+
+	// Find the generic methods stored on N.
+	gm, gn := N.Method(0), N.Method(1)
+	if gm.Name() == "n" {
+		gm, gn = gn, gm
+	}
+
+	// Collect objects from info.
+	var dm, dn *Func   // the declared methods
+	var dmm, dmn *Func // the methods used in the body of m
+	for _, decl := range f.DeclList {
+		fdecl, ok := decl.(*syntax.FuncDecl)
+		if !ok {
+			continue
+		}
+		def := info.Defs[fdecl.Name].(*Func)
+		switch fdecl.Name.Value {
+		case "m":
+			dm = def
+			syntax.Inspect(fdecl.Body, func(n syntax.Node) bool {
+				if call, ok := n.(*syntax.CallExpr); ok {
+					sel := call.Fun.(*syntax.SelectorExpr)
+					use := info.Uses[sel.Sel].(*Func)
+					selection := info.Selections[sel]
+					if selection.Kind() != MethodVal {
+						t.Errorf("Selection kind = %v, want %v", selection.Kind(), MethodVal)
+					}
+					if selection.Obj() != use {
+						t.Errorf("info.Selections contains %v, want %v", selection.Obj(), use)
+					}
+					switch sel.Sel.Value {
+					case "m":
+						dmm = use
+					case "n":
+						dmn = use
+					}
+				}
+				return true
+			})
+		case "n":
+			dn = def
+		}
+	}
+
+	if gm != dm {
+		t.Errorf(`N.Method(...) returns %v for "m", but Info.Defs has %v`, gm, dm)
+	}
+	if gn != dn {
+		t.Errorf(`N.Method(...) returns %v for "m", but Info.Defs has %v`, gm, dm)
+	}
+	if dmm != dm {
+		t.Errorf(`Inside "m", r.m uses %v, want the defined func %v`, dmm, dm)
+	}
+	if dmn == dn {
+		t.Errorf(`Inside "m", r.n uses %v, want a func distinct from %v`, dmm, dm)
+	}
+}
+
 func TestImplicitsInfo(t *testing.T) {
 	testenv.MustHaveGoBuild(t)
 
@@ -725,6 +827,17 @@ func TestImplicitsInfo(t *testing.T) {
 		{`package p8; func f(int) {}`, "field: var  int"},
 		{`package p9; func f() (complex64) { return 0 }`, "field: var  complex64"},
 		{`package p10; type T struct{}; func (*T) f() {}`, "field: var  *p10.T"},
+
+		// Tests using generics.
+		{`package f0; func f[T any](x int) {}`, ""}, // no Implicits entry
+		{`package f1; func f[T any](int) {}`, "field: var  int"},
+		{`package f2; func f[T any](T) {}`, "field: var  T"},
+		{`package f3; func f[T any]() (complex64) { return 0 }`, "field: var  complex64"},
+		{`package f4; func f[T any](t T) (T) { return t }`, "field: var  T"},
+		{`package t0; type T[A any] struct{}; func (*T[_]) f() {}`, "field: var  *t0.T[_]"},
+		{`package t1; type T[A any] struct{}; func _(x interface{}) { switch t := x.(type) { case T[int]: _ = t } }`, "caseClause: var t t1.T[int]"},
+		{`package t2; type T[A any] struct{}; func _[P any](x interface{}) { switch t := x.(type) { case T[P]: _ = t } }`, "caseClause: var t t2.T[P]"},
+		{`package t3; func _[P any](x interface{}) { switch t := x.(type) { case P: _ = t } }`, "caseClause: var t P"},
 	}
 
 	for _, test := range tests {
diff --git a/src/cmd/compile/internal/types2/decl.go b/src/cmd/compile/internal/types2/decl.go
index d9e926b856..0e8f5085ba 100644
--- a/src/cmd/compile/internal/types2/decl.go
+++ b/src/cmd/compile/internal/types2/decl.go
@@ -66,12 +66,6 @@ func (check *Checker) objDecl(obj Object, def *Named) {
 		}()
 	}
 
-	// Funcs with m.instRecv set have not yet be completed. Complete them now
-	// so that they have a type when objDecl exits.
-	if m, _ := obj.(*Func); m != nil && m.instRecv != nil {
-		check.completeMethod(nil, m)
-	}
-
 	// Checking the declaration of obj means inferring its type
 	// (and possibly its value, for constants).
 	// An object's type (and thus the object) may be in one of
@@ -643,6 +637,7 @@ func (check *Checker) collectMethods(obj *TypeName) {
 	// and field names must be distinct."
 	base, _ := obj.typ.(*Named) // shouldn't fail but be conservative
 	if base != nil {
+		assert(base.targs.Len() == 0) // collectMethods should not be called on an instantiated type
 		u := base.under()
 		if t, _ := u.(*Struct); t != nil {
 			for _, fld := range t.fields {
@@ -655,7 +650,8 @@ func (check *Checker) collectMethods(obj *TypeName) {
 		// Checker.Files may be called multiple times; additional package files
 		// may add methods to already type-checked types. Add pre-existing methods
 		// so that we can detect redeclarations.
-		for _, m := range base.methods {
+		for i := 0; i < base.methods.Len(); i++ {
+			m := base.methods.At(i, nil)
 			assert(m.name != "_")
 			assert(mset.insert(m) == nil)
 		}
@@ -687,7 +683,7 @@ func (check *Checker) collectMethods(obj *TypeName) {
 
 		if base != nil {
 			base.resolve(nil) // TODO(mdempsky): Probably unnecessary.
-			base.methods = append(base.methods, m)
+			base.AddMethod(m)
 		}
 	}
 }
diff --git a/src/cmd/compile/internal/types2/instantiate.go b/src/cmd/compile/internal/types2/instantiate.go
index 5d5a660419..e520d0ffa3 100644
--- a/src/cmd/compile/internal/types2/instantiate.go
+++ b/src/cmd/compile/internal/types2/instantiate.go
@@ -78,7 +78,7 @@ func (check *Checker) instance(pos syntax.Pos, orig Type, targs []Type, ctxt *Co
 		tname := NewTypeName(pos, orig.obj.pkg, orig.obj.name, nil)
 		named := check.newNamed(tname, orig, nil, nil, nil) // underlying, tparams, and methods are set when named is resolved
 		named.targs = newTypeList(targs)
-		named.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, []*Func) {
+		named.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, *methodList) {
 			return expandNamed(ctxt, n, pos)
 		}
 		res = named
diff --git a/src/cmd/compile/internal/types2/lookup.go b/src/cmd/compile/internal/types2/lookup.go
index 3e55c07b67..408832846d 100644
--- a/src/cmd/compile/internal/types2/lookup.go
+++ b/src/cmd/compile/internal/types2/lookup.go
@@ -144,7 +144,7 @@ func lookupFieldOrMethod(T Type, addressable, checkFold bool, pkg *Package, name
 
 				// look for a matching attached method
 				named.resolve(nil)
-				if i, m := lookupMethodFold(named.methods, pkg, name, checkFold); m != nil {
+				if i, m := named.lookupMethodFold(pkg, name, checkFold); m != nil {
 					// potential match
 					// caution: method may not have a proper signature yet
 					index = concat(e.index, i)
diff --git a/src/cmd/compile/internal/types2/methodlist.go b/src/cmd/compile/internal/types2/methodlist.go
new file mode 100644
index 0000000000..ba10159ea2
--- /dev/null
+++ b/src/cmd/compile/internal/types2/methodlist.go
@@ -0,0 +1,79 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types2
+
+import "sync"
+
+// methodList holds a list of methods that may be lazily resolved by a provided
+// resolution method.
+type methodList struct {
+	methods []*Func
+
+	// guards synchronizes the instantiation of lazy methods. For lazy method
+	// lists, guards is non-nil and of the length passed to newLazyMethodList.
+	// For non-lazy method lists, guards is nil.
+	guards *[]sync.Once
+}
+
+// newMethodList creates a non-lazy method list holding the given methods.
+func newMethodList(methods []*Func) *methodList {
+	return &methodList{methods: methods}
+}
+
+// newLazyMethodList creates a lazy method list of the given length. Methods
+// may be resolved lazily for a given index by providing a resolver function.
+func newLazyMethodList(length int) *methodList {
+	guards := make([]sync.Once, length)
+	return &methodList{
+		methods: make([]*Func, length),
+		guards:  &guards,
+	}
+}
+
+// isLazy reports whether the receiver is a lazy method list.
+func (l *methodList) isLazy() bool {
+	return l != nil && l.guards != nil
+}
+
+// Add appends a method to the method list if not not already present. Add
+// panics if the receiver is lazy.
+func (l *methodList) Add(m *Func) {
+	assert(!l.isLazy())
+	if i, _ := lookupMethod(l.methods, m.pkg, m.name); i < 0 {
+		l.methods = append(l.methods, m)
+	}
+}
+
+// LookupFold looks up the method identified by pkg and name in the receiver.
+// LookupFold panics if the receiver is lazy. If checkFold is true, it matches
+// a method name if the names are equal with case folding.
+func (l *methodList) LookupFold(pkg *Package, name string, checkFold bool) (int, *Func) {
+	assert(!l.isLazy())
+	if l == nil {
+		return -1, nil
+	}
+	return lookupMethodFold(l.methods, pkg, name, checkFold)
+}
+
+// Len returns the length of the method list.
+func (l *methodList) Len() int {
+	if l == nil {
+		return 0
+	}
+	return len(l.methods)
+}
+
+// At returns the i'th method of the method list. At panics if i is out of
+// bounds, or if the receiver is lazy and resolve is nil.
+func (l *methodList) At(i int, resolve func() *Func) *Func {
+	if !l.isLazy() {
+		return l.methods[i]
+	}
+	assert(resolve != nil)
+	(*l.guards)[i].Do(func() {
+		l.methods[i] = resolve()
+	})
+	return l.methods[i]
+}
diff --git a/src/cmd/compile/internal/types2/methodlist_test.go b/src/cmd/compile/internal/types2/methodlist_test.go
new file mode 100644
index 0000000000..7a183ac7f9
--- /dev/null
+++ b/src/cmd/compile/internal/types2/methodlist_test.go
@@ -0,0 +1,40 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types2
+
+import (
+	"testing"
+)
+
+func TestLazyMethodList(t *testing.T) {
+	l := newLazyMethodList(2)
+
+	if got := l.Len(); got != 2 {
+		t.Fatalf("Len() = %d, want 2", got)
+	}
+
+	f0 := NewFunc(nopos, nil, "f0", nil)
+	f1 := NewFunc(nopos, nil, "f1", nil)
+
+	// Verify that methodList.At is idempotent, by calling it repeatedly with a
+	// resolve func that returns different pointer values (f0 or f1).
+	steps := []struct {
+		index   int
+		resolve *Func // the *Func returned by the resolver
+		want    *Func // the actual *Func returned by methodList.At
+	}{
+		{0, f0, f0},
+		{0, f1, f0},
+		{1, f1, f1},
+		{1, f0, f1},
+	}
+
+	for i, step := range steps {
+		got := l.At(step.index, func() *Func { return step.resolve })
+		if got != step.want {
+			t.Errorf("step %d: At(%d, ...) = %s, want %s", i, step.index, got.Name(), step.want.Name())
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/types2/named.go b/src/cmd/compile/internal/types2/named.go
index 3ba53052d7..ed33a9ddf7 100644
--- a/src/cmd/compile/internal/types2/named.go
+++ b/src/cmd/compile/internal/types2/named.go
@@ -18,10 +18,16 @@ type Named struct {
 	underlying Type           // possibly a *Named during setup; never a *Named once set up completely
 	tparams    *TypeParamList // type parameters, or nil
 	targs      *TypeList      // type arguments (after instantiation), or nil
-	methods    []*Func        // methods declared for this type (not the method set of this type); signatures are type-checked lazily
+
+	// methods declared for this type (not the method set of this type).
+	// Signatures are type-checked lazily.
+	// For non-instantiated types, this is a fully populated list of methods. For
+	// instantiated types, this is a 'lazy' list, and methods are instantiated
+	// when they are first accessed.
+	methods *methodList
 
 	// resolver may be provided to lazily resolve type parameters, underlying, and methods.
-	resolver func(*Context, *Named) (tparams *TypeParamList, underlying Type, methods []*Func)
+	resolver func(*Context, *Named) (tparams *TypeParamList, underlying Type, methods *methodList)
 	once     sync.Once // ensures that tparams, underlying, and methods are resolved before accessing
 }
 
@@ -32,7 +38,7 @@ func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
 	if _, ok := underlying.(*Named); ok {
 		panic("underlying type must not be *Named")
 	}
-	return (*Checker)(nil).newNamed(obj, nil, underlying, nil, methods)
+	return (*Checker)(nil).newNamed(obj, nil, underlying, nil, newMethodList(methods))
 }
 
 func (t *Named) resolve(ctxt *Context) *Named {
@@ -56,7 +62,7 @@ func (t *Named) resolve(ctxt *Context) *Named {
 }
 
 // newNamed is like NewNamed but with a *Checker receiver and additional orig argument.
-func (check *Checker) newNamed(obj *TypeName, orig *Named, underlying Type, tparams *TypeParamList, methods []*Func) *Named {
+func (check *Checker) newNamed(obj *TypeName, orig *Named, underlying Type, tparams *TypeParamList, methods *methodList) *Named {
 	typ := &Named{check: check, obj: obj, orig: orig, fromRHS: underlying, underlying: underlying, tparams: tparams, methods: methods}
 	if typ.orig == nil {
 		typ.orig = typ
@@ -97,10 +103,72 @@ func (t *Named) SetTypeParams(tparams []*TypeParam) {
 func (t *Named) TypeArgs() *TypeList { return t.targs }
 
 // NumMethods returns the number of explicit methods whose receiver is named type t.
-func (t *Named) NumMethods() int { return len(t.resolve(nil).methods) }
+func (t *Named) NumMethods() int { return t.resolve(nil).methods.Len() }
 
 // Method returns the i'th method of named type t for 0 <= i < t.NumMethods().
-func (t *Named) Method(i int) *Func { return t.resolve(nil).methods[i] }
+func (t *Named) Method(i int) *Func {
+	t.resolve(nil)
+	return t.methods.At(i, func() *Func {
+		return t.instantiateMethod(i)
+	})
+}
+
+// instiateMethod instantiates the i'th method for an instantiated receiver.
+func (t *Named) instantiateMethod(i int) *Func {
+	assert(t.TypeArgs().Len() > 0) // t must be an instance
+
+	// t.orig.methods is not lazy. origm is the method instantiated with its
+	// receiver type parameters (the "origin" method).
+	origm := t.orig.Method(i)
+	assert(origm != nil)
+
+	check := t.check
+	// Ensure that the original method is type-checked.
+	if check != nil {
+		check.objDecl(origm, nil)
+	}
+
+	origSig := origm.typ.(*Signature)
+	rbase, _ := deref(origSig.Recv().Type())
+
+	// If rbase is t, then origm is already the instantiated method we're looking
+	// for. In this case, we return origm to preserve the invariant that
+	// traversing Method->Receiver Type->Method should get back to the same
+	// method.
+	//
+	// This occurs if t is instantiated with the receiver type parameters, as in
+	// the use of m in func (r T[_]) m() { r.m() }.
+	if rbase == t {
+		return origm
+	}
+
+	sig := origSig
+	// We can only substitute if we have a correspondence between type arguments
+	// and type parameters. This check is necessary in the presence of invalid
+	// code.
+	if origSig.RecvTypeParams().Len() == t.targs.Len() {
+		ctxt := check.bestContext(nil)
+		smap := makeSubstMap(origSig.RecvTypeParams().list(), t.targs.list())
+		sig = check.subst(origm.pos, origSig, smap, ctxt).(*Signature)
+	}
+
+	if sig == origSig {
+		// No substitution occurred, but we still need to create a new signature to
+		// hold the instantiated receiver.
+		copy := *origSig
+		sig = &copy
+	}
+
+	var rtyp Type
+	if origm.hasPtrRecv() {
+		rtyp = NewPointer(t)
+	} else {
+		rtyp = t
+	}
+
+	sig.recv = NewParam(origSig.recv.pos, origSig.recv.pkg, origSig.recv.name, rtyp)
+	return NewFunc(origm.pos, origm.pkg, origm.name, sig)
+}
 
 // SetUnderlying sets the underlying type and marks t as complete.
 // t must not have type arguments.
@@ -123,9 +191,10 @@ func (t *Named) SetUnderlying(underlying Type) {
 func (t *Named) AddMethod(m *Func) {
 	assert(t.targs.Len() == 0)
 	t.resolve(nil)
-	if i, _ := lookupMethod(t.methods, m.pkg, m.name); i < 0 {
-		t.methods = append(t.methods, m)
+	if t.methods == nil {
+		t.methods = newMethodList(nil)
 	}
+	t.methods.Add(m)
 }
 
 func (t *Named) Underlying() Type { return t.resolve(nil).underlying }
@@ -228,6 +297,19 @@ func (n *Named) setUnderlying(typ Type) {
 	}
 }
 
+func (n *Named) lookupMethodFold(pkg *Package, name string, checkFold bool) (int, *Func) {
+	n.resolve(nil)
+	// If n is an instance, we may not have yet instantiated all of its methods.
+	// Look up the method index in orig, and only instantiate method at the
+	// matching index (if any).
+	i, _ := n.orig.methods.LookupFold(pkg, name, checkFold)
+	if i < 0 {
+		return -1, nil
+	}
+	// For instances, m.Method(i) will be different from the orig method.
+	return i, n.Method(i)
+}
+
 // bestContext returns the best available context. In order of preference:
 // - the given ctxt, if non-nil
 // - check.ctxt, if check is non-nil
@@ -247,7 +329,7 @@ func (check *Checker) bestContext(ctxt *Context) *Context {
 
 // expandNamed ensures that the underlying type of n is instantiated.
 // The underlying type will be Typ[Invalid] if there was an error.
-func expandNamed(ctxt *Context, n *Named, instPos syntax.Pos) (tparams *TypeParamList, underlying Type, methods []*Func) {
+func expandNamed(ctxt *Context, n *Named, instPos syntax.Pos) (tparams *TypeParamList, underlying Type, methods *methodList) {
 	n.orig.resolve(ctxt)
 	assert(n.orig.underlying != nil)
 
@@ -269,80 +351,13 @@ func expandNamed(ctxt *Context, n *Named, instPos syntax.Pos) (tparams *TypePara
 
 		smap := makeSubstMap(n.orig.tparams.list(), n.targs.list())
 		underlying = n.check.subst(instPos, n.orig.underlying, smap, ctxt)
-
-		for i := 0; i < n.orig.NumMethods(); i++ {
-			origm := n.orig.Method(i)
-
-			// During type checking origm may not have a fully set up type, so defer
-			// instantiation of its signature until later.
-			m := NewFunc(origm.pos, origm.pkg, origm.name, nil)
-			m.hasPtrRecv_ = origm.hasPtrRecv()
-			// Setting instRecv here allows us to complete later (we need the
-			// instRecv to get targs and the original method).
-			m.instRecv = n
-
-			methods = append(methods, m)
-		}
 	} else {
 		underlying = Typ[Invalid]
 	}
 
-	// Methods should not escape the type checker API without being completed. If
-	// we're in the context of a type checking pass, we need to defer this until
-	// later (not all methods may have types).
-	completeMethods := func() {
-		for _, m := range methods {
-			if m.instRecv != nil {
-				check.completeMethod(ctxt, m)
-			}
-		}
-	}
-	if check != nil {
-		check.later(completeMethods)
-	} else {
-		completeMethods()
-	}
-
-	return n.orig.tparams, underlying, methods
-}
-
-func (check *Checker) completeMethod(ctxt *Context, m *Func) {
-	assert(m.instRecv != nil)
-	rbase := m.instRecv
-	m.instRecv = nil
-	m.setColor(black)
-
-	assert(rbase.TypeArgs().Len() > 0)
-
-	// Look up the original method.
-	_, orig := lookupMethod(rbase.orig.methods, rbase.obj.pkg, m.name)
-	assert(orig != nil)
-	if check != nil {
-		check.objDecl(orig, nil)
-	}
-	origSig := orig.typ.(*Signature)
-	if origSig.RecvTypeParams().Len() != rbase.targs.Len() {
-		m.typ = origSig // or new(Signature), but we can't use Typ[Invalid]: Funcs must have Signature type
-		return          // error reported elsewhere
-	}
-
-	smap := makeSubstMap(origSig.RecvTypeParams().list(), rbase.targs.list())
-	sig := check.subst(orig.pos, origSig, smap, ctxt).(*Signature)
-	if sig == origSig {
-		// No substitution occurred, but we still need to create a new signature to
-		// hold the instantiated receiver.
-		copy := *origSig
-		sig = &copy
-	}
-	var rtyp Type
-	if m.hasPtrRecv() {
-		rtyp = NewPointer(rbase)
-	} else {
-		rtyp = rbase
-	}
-	sig.recv = NewParam(origSig.recv.pos, origSig.recv.pkg, origSig.recv.name, rtyp)
+	mlist := newLazyMethodList(n.orig.methods.Len())
 
-	m.typ = sig
+	return n.orig.tparams, underlying, mlist
 }
 
 // safeUnderlying returns the underlying of typ without expanding instances, to
diff --git a/src/cmd/compile/internal/types2/object.go b/src/cmd/compile/internal/types2/object.go
index c7c64ca9d5..08d37cb256 100644
--- a/src/cmd/compile/internal/types2/object.go
+++ b/src/cmd/compile/internal/types2/object.go
@@ -281,7 +281,7 @@ func NewTypeName(pos syntax.Pos, pkg *Package, name string, typ Type) *TypeName
 func NewTypeNameLazy(pos syntax.Pos, pkg *Package, name string, load func(named *Named) (tparams []*TypeParam, underlying Type, methods []*Func)) *TypeName {
 	obj := NewTypeName(pos, pkg, name, nil)
 
-	resolve := func(_ *Context, t *Named) (*TypeParamList, Type, []*Func) {
+	resolve := func(_ *Context, t *Named) (*TypeParamList, Type, *methodList) {
 		tparams, underlying, methods := load(t)
 
 		switch underlying.(type) {
@@ -289,7 +289,7 @@ func NewTypeNameLazy(pos syntax.Pos, pkg *Package, name string, load func(named
 			panic(fmt.Sprintf("invalid underlying type %T", t.underlying))
 		}
 
-		return bindTParams(tparams), underlying, methods
+		return bindTParams(tparams), underlying, newMethodList(methods)
 	}
 
 	NewNamed(obj, nil, nil).resolver = resolve
@@ -365,8 +365,7 @@ func (*Var) isDependency() {} // a variable may be a dependency of an initializa
 // An abstract method may belong to many interfaces due to embedding.
 type Func struct {
 	object
-	instRecv    *Named // if non-nil, the receiver type for an incomplete instance method
-	hasPtrRecv_ bool   // only valid for methods that don't have a type yet; use hasPtrRecv() to read
+	hasPtrRecv_ bool // only valid for methods that don't have a type yet; use hasPtrRecv() to read
 }
 
 // NewFunc returns a new function with the given signature, representing
@@ -377,7 +376,7 @@ func NewFunc(pos syntax.Pos, pkg *Package, name string, sig *Signature) *Func {
 	if sig != nil {
 		typ = sig
 	}
-	return &Func{object{nil, pos, pkg, name, typ, 0, colorFor(typ), nopos}, nil, false}
+	return &Func{object{nil, pos, pkg, name, typ, 0, colorFor(typ), nopos}, false}
 }
 
 // FullName returns the package- or receiver-type-qualified name of
diff --git a/src/cmd/compile/internal/types2/sizeof_test.go b/src/cmd/compile/internal/types2/sizeof_test.go
index 52a1df1aa4..14020050a9 100644
--- a/src/cmd/compile/internal/types2/sizeof_test.go
+++ b/src/cmd/compile/internal/types2/sizeof_test.go
@@ -31,7 +31,7 @@ func TestSizeof(t *testing.T) {
 		{Interface{}, 44, 88},
 		{Map{}, 16, 32},
 		{Chan{}, 12, 24},
-		{Named{}, 64, 120},
+		{Named{}, 56, 104},
 		{TypeParam{}, 28, 48},
 		{term{}, 12, 24},
 
@@ -40,7 +40,7 @@ func TestSizeof(t *testing.T) {
 		{Const{}, 64, 104},
 		{TypeName{}, 56, 88},
 		{Var{}, 60, 96},
-		{Func{}, 64, 104},
+		{Func{}, 60, 96},
 		{Label{}, 60, 96},
 		{Builtin{}, 60, 96},
 		{Nil{}, 56, 88},
diff --git a/src/cmd/compile/internal/types2/typexpr.go b/src/cmd/compile/internal/types2/typexpr.go
index 92c3e642fe..de778fb010 100644
--- a/src/cmd/compile/internal/types2/typexpr.go
+++ b/src/cmd/compile/internal/types2/typexpr.go
@@ -452,7 +452,7 @@ func (check *Checker) instantiatedType(x syntax.Expr, xlist []syntax.Expr, def *
 	}
 	def.setUnderlying(inst)
 
-	inst.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, []*Func) {
+	inst.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, *methodList) {
 		tparams := orig.TypeParams().list()
 
 		inferred := targs
diff --git a/src/go/types/api_test.go b/src/go/types/api_test.go
index 7986534e78..5c61e54360 100644
--- a/src/go/types/api_test.go
+++ b/src/go/types/api_test.go
@@ -632,6 +632,11 @@ func TestDefsInfo(t *testing.T) {
 		{`package p3; type x int`, `x`, `type p3.x int`},
 		{`package p4; func f()`, `f`, `func p4.f()`},
 		{`package p5; func f() int { x, _ := 1, 2; return x }`, `_`, `var _ int`},
+
+		// Tests using generics.
+		{`package generic_g0; type x[T any] int`, `x`, `type generic_g0.x[T any] int`},
+		{`package generic_g1; func f[T any]() {}`, `f`, `func generic_g1.f[T any]()`},
+		{`package generic_g2; type x[T any] int; func (*x[_]) m() {}`, `m`, `func (*generic_g2.x[_]).m()`},
 	}
 
 	for _, test := range tests {
@@ -670,6 +675,20 @@ func TestUsesInfo(t *testing.T) {
 		{`package p2; func _() { _ = x }; var x int`, `x`, `var p2.x int`},
 		{`package p3; func _() { type _ x }; type x int`, `x`, `type p3.x int`},
 		{`package p4; func _() { _ = f }; func f()`, `f`, `func p4.f()`},
+
+		// Tests using generics.
+		{`package generic_g0; func _[T any]() { _ = x }; const x = 42`, `x`, `const generic_g0.x untyped int`},
+		{`package generic_g1; func _[T any](x T) { }`, `T`, `type parameter T any`},
+		{`package generic_g2; type N[A any] int; var _ N[int]`, `N`, `type generic_g2.N[A any] int`},
+		{`package generic_g3; type N[A any] int; func (N[_]) m() {}`, `N`, `type generic_g3.N[A any] int`},
+
+		// Uses of fields are instantiated.
+		{`package generic_s1; type N[A any] struct{ a A }; var f = N[int]{}.a`, `a`, `field a int`},
+		{`package generic_s1; type N[A any] struct{ a A }; func (r N[B]) m(b B) { r.a = b }`, `a`, `field a B`},
+
+		// Uses of methods are uses of the instantiated method.
+		{`package generic_m0; type N[A any] int; func (r N[B]) m() { r.n() }; func (N[C]) n() {}`, `n`, `func (generic_m0.N[B]).n()`},
+		{`package generic_m1; type N[A any] int; func (r N[B]) m() { }; var f = N[int].m`, `m`, `func (generic_m1.N[int]).m()`},
 	}
 
 	for _, test := range tests {
@@ -697,6 +716,90 @@ func TestUsesInfo(t *testing.T) {
 	}
 }
 
+func TestGenericMethodInfo(t *testing.T) {
+	src := `package p
+
+type N[A any] int
+
+func (r N[B]) m() { r.m(); r.n() }
+
+func (r *N[C]) n() {  }
+`
+	fset := token.NewFileSet()
+	f, err := parser.ParseFile(fset, "p.go", src, 0)
+	if err != nil {
+		t.Fatal(err)
+	}
+	info := Info{
+		Defs:       make(map[*ast.Ident]Object),
+		Uses:       make(map[*ast.Ident]Object),
+		Selections: make(map[*ast.SelectorExpr]*Selection),
+	}
+	var conf Config
+	pkg, err := conf.Check("p", fset, []*ast.File{f}, &info)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	N := pkg.Scope().Lookup("N").Type().(*Named)
+
+	// Find the generic methods stored on N.
+	gm, gn := N.Method(0), N.Method(1)
+	if gm.Name() == "n" {
+		gm, gn = gn, gm
+	}
+
+	// Collect objects from info.
+	var dm, dn *Func   // the declared methods
+	var dmm, dmn *Func // the methods used in the body of m
+	for _, decl := range f.Decls {
+		fdecl, ok := decl.(*ast.FuncDecl)
+		if !ok {
+			continue
+		}
+		def := info.Defs[fdecl.Name].(*Func)
+		switch fdecl.Name.Name {
+		case "m":
+			dm = def
+			ast.Inspect(fdecl.Body, func(n ast.Node) bool {
+				if call, ok := n.(*ast.CallExpr); ok {
+					sel := call.Fun.(*ast.SelectorExpr)
+					use := info.Uses[sel.Sel].(*Func)
+					selection := info.Selections[sel]
+					if selection.Kind() != MethodVal {
+						t.Errorf("Selection kind = %v, want %v", selection.Kind(), MethodVal)
+					}
+					if selection.Obj() != use {
+						t.Errorf("info.Selections contains %v, want %v", selection.Obj(), use)
+					}
+					switch sel.Sel.Name {
+					case "m":
+						dmm = use
+					case "n":
+						dmn = use
+					}
+				}
+				return true
+			})
+		case "n":
+			dn = def
+		}
+	}
+
+	if gm != dm {
+		t.Errorf(`N.Method(...) returns %v for "m", but Info.Defs has %v`, gm, dm)
+	}
+	if gn != dn {
+		t.Errorf(`N.Method(...) returns %v for "m", but Info.Defs has %v`, gm, dm)
+	}
+	if dmm != dm {
+		t.Errorf(`Inside "m", r.m uses %v, want the defined func %v`, dmm, dm)
+	}
+	if dmn == dn {
+		t.Errorf(`Inside "m", r.n uses %v, want a func distinct from %v`, dmm, dm)
+	}
+}
+
 func TestImplicitsInfo(t *testing.T) {
 	testenv.MustHaveGoBuild(t)
 
@@ -717,6 +820,17 @@ func TestImplicitsInfo(t *testing.T) {
 		{`package p8; func f(int) {}`, "field: var  int"},
 		{`package p9; func f() (complex64) { return 0 }`, "field: var  complex64"},
 		{`package p10; type T struct{}; func (*T) f() {}`, "field: var  *p10.T"},
+
+		// Tests using generics.
+		{`package generic_f0; func f[T any](x int) {}`, ""}, // no Implicits entry
+		{`package generic_f1; func f[T any](int) {}`, "field: var  int"},
+		{`package generic_f2; func f[T any](T) {}`, "field: var  T"},
+		{`package generic_f3; func f[T any]() (complex64) { return 0 }`, "field: var  complex64"},
+		{`package generic_f4; func f[T any](t T) (T) { return t }`, "field: var  T"},
+		{`package generic_t0; type T[A any] struct{}; func (*T[_]) f() {}`, "field: var  *generic_t0.T[_]"},
+		{`package generic_t1; type T[A any] struct{}; func _(x interface{}) { switch t := x.(type) { case T[int]: _ = t } }`, "caseClause: var t generic_t1.T[int]"},
+		{`package generic_t2; type T[A any] struct{}; func _[P any](x interface{}) { switch t := x.(type) { case T[P]: _ = t } }`, "caseClause: var t generic_t2.T[P]"},
+		{`package generic_t3; func _[P any](x interface{}) { switch t := x.(type) { case P: _ = t } }`, "caseClause: var t P"},
 	}
 
 	for _, test := range tests {
diff --git a/src/go/types/decl.go b/src/go/types/decl.go
index 3fc4487309..cd6f709a56 100644
--- a/src/go/types/decl.go
+++ b/src/go/types/decl.go
@@ -65,12 +65,6 @@ func (check *Checker) objDecl(obj Object, def *Named) {
 		}()
 	}
 
-	// Funcs with m.instRecv set have not yet be completed. Complete them now
-	// so that they have a type when objDecl exits.
-	if m, _ := obj.(*Func); m != nil && m.instRecv != nil {
-		check.completeMethod(nil, m)
-	}
-
 	// Checking the declaration of obj means inferring its type
 	// (and possibly its value, for constants).
 	// An object's type (and thus the object) may be in one of
@@ -719,6 +713,7 @@ func (check *Checker) collectMethods(obj *TypeName) {
 	// and field names must be distinct."
 	base, _ := obj.typ.(*Named) // shouldn't fail but be conservative
 	if base != nil {
+		assert(base.targs.Len() == 0) // collectMethods should not be called on an instantiated type
 		u := base.under()
 		if t, _ := u.(*Struct); t != nil {
 			for _, fld := range t.fields {
@@ -731,7 +726,8 @@ func (check *Checker) collectMethods(obj *TypeName) {
 		// Checker.Files may be called multiple times; additional package files
 		// may add methods to already type-checked types. Add pre-existing methods
 		// so that we can detect redeclarations.
-		for _, m := range base.methods {
+		for i := 0; i < base.methods.Len(); i++ {
+			m := base.methods.At(i, nil)
 			assert(m.name != "_")
 			assert(mset.insert(m) == nil)
 		}
@@ -757,7 +753,7 @@ func (check *Checker) collectMethods(obj *TypeName) {
 
 		if base != nil {
 			base.resolve(nil) // TODO(mdempsky): Probably unnecessary.
-			base.methods = append(base.methods, m)
+			base.AddMethod(m)
 		}
 	}
 }
diff --git a/src/go/types/instantiate.go b/src/go/types/instantiate.go
index 1a0823575b..dc1c2029bc 100644
--- a/src/go/types/instantiate.go
+++ b/src/go/types/instantiate.go
@@ -78,7 +78,7 @@ func (check *Checker) instance(pos token.Pos, orig Type, targs []Type, ctxt *Con
 		tname := NewTypeName(pos, orig.obj.pkg, orig.obj.name, nil)
 		named := check.newNamed(tname, orig, nil, nil, nil) // underlying, tparams, and methods are set when named is resolved
 		named.targs = newTypeList(targs)
-		named.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, []*Func) {
+		named.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, *methodList) {
 			return expandNamed(ctxt, n, pos)
 		}
 		res = named
diff --git a/src/go/types/lookup.go b/src/go/types/lookup.go
index cc6be7493c..8198b058bd 100644
--- a/src/go/types/lookup.go
+++ b/src/go/types/lookup.go
@@ -142,7 +142,7 @@ func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (o
 
 				// look for a matching attached method
 				named.resolve(nil)
-				if i, m := lookupMethod(named.methods, pkg, name); m != nil {
+				if i, m := named.lookupMethod(pkg, name); m != nil {
 					// potential match
 					// caution: method may not have a proper signature yet
 					index = concat(e.index, i)
diff --git a/src/go/types/methodlist.go b/src/go/types/methodlist.go
new file mode 100644
index 0000000000..10a2a323a8
--- /dev/null
+++ b/src/go/types/methodlist.go
@@ -0,0 +1,78 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types
+
+import "sync"
+
+// methodList holds a list of methods that may be lazily resolved by a provided
+// resolution method.
+type methodList struct {
+	methods []*Func
+
+	// guards synchronizes the instantiation of lazy methods. For lazy method
+	// lists, guards is non-nil and of the length passed to newLazyMethodList.
+	// For non-lazy method lists, guards is nil.
+	guards *[]sync.Once
+}
+
+// newMethodList creates a non-lazy method list holding the given methods.
+func newMethodList(methods []*Func) *methodList {
+	return &methodList{methods: methods}
+}
+
+// newLazyMethodList creates a lazy method list of the given length. Methods
+// may be resolved lazily for a given index by providing a resolver function.
+func newLazyMethodList(length int) *methodList {
+	guards := make([]sync.Once, length)
+	return &methodList{
+		methods: make([]*Func, length),
+		guards:  &guards,
+	}
+}
+
+// isLazy reports whether the receiver is a lazy method list.
+func (l *methodList) isLazy() bool {
+	return l != nil && l.guards != nil
+}
+
+// Add appends a method to the method list if not not already present. Add
+// panics if the receiver is lazy.
+func (l *methodList) Add(m *Func) {
+	assert(!l.isLazy())
+	if i, _ := lookupMethod(l.methods, m.pkg, m.name); i < 0 {
+		l.methods = append(l.methods, m)
+	}
+}
+
+// Lookup looks up the method identified by pkg and name in the receiver.
+// Lookup panics if the receiver is lazy.
+func (l *methodList) Lookup(pkg *Package, name string) (int, *Func) {
+	assert(!l.isLazy())
+	if l == nil {
+		return -1, nil
+	}
+	return lookupMethod(l.methods, pkg, name)
+}
+
+// Len returns the length of the method list.
+func (l *methodList) Len() int {
+	if l == nil {
+		return 0
+	}
+	return len(l.methods)
+}
+
+// At returns the i'th method of the method list. At panics if i is out of
+// bounds, or if the receiver is lazy and resolve is nil.
+func (l *methodList) At(i int, resolve func() *Func) *Func {
+	if !l.isLazy() {
+		return l.methods[i]
+	}
+	assert(resolve != nil)
+	(*l.guards)[i].Do(func() {
+		l.methods[i] = resolve()
+	})
+	return l.methods[i]
+}
diff --git a/src/go/types/methodlist_test.go b/src/go/types/methodlist_test.go
new file mode 100644
index 0000000000..e628bce767
--- /dev/null
+++ b/src/go/types/methodlist_test.go
@@ -0,0 +1,41 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types
+
+import (
+	"go/token"
+	"testing"
+)
+
+func TestLazyMethodList(t *testing.T) {
+	l := newLazyMethodList(2)
+
+	if got := l.Len(); got != 2 {
+		t.Fatalf("Len() = %d, want 2", got)
+	}
+
+	f0 := NewFunc(token.NoPos, nil, "f0", nil)
+	f1 := NewFunc(token.NoPos, nil, "f1", nil)
+
+	// Verify that methodList.At is idempotent, by calling it repeatedly with a
+	// resolve func that returns different pointer values (f0 or f1).
+	steps := []struct {
+		index   int
+		resolve *Func // the *Func returned by the resolver
+		want    *Func // the actual *Func returned by methodList.At
+	}{
+		{0, f0, f0},
+		{0, f1, f0},
+		{1, f1, f1},
+		{1, f0, f1},
+	}
+
+	for i, step := range steps {
+		got := l.At(step.index, func() *Func { return step.resolve })
+		if got != step.want {
+			t.Errorf("step %d: At(%d, ...) = %s, want %s", i, step.index, got.Name(), step.want.Name())
+		}
+	}
+}
diff --git a/src/go/types/methodset.go b/src/go/types/methodset.go
index 5c3bc39271..c1d1e93e59 100644
--- a/src/go/types/methodset.go
+++ b/src/go/types/methodset.go
@@ -125,7 +125,9 @@ func NewMethodSet(T Type) *MethodSet {
 				}
 				seen[named] = true
 
-				mset = mset.add(named.methods, e.index, e.indirect, e.multiples)
+				for i := 0; i < named.NumMethods(); i++ {
+					mset = mset.addOne(named.Method(i), concat(e.index, i), e.indirect, e.multiples)
+				}
 			}
 
 			switch t := under(typ).(type) {
@@ -214,23 +216,28 @@ func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool)
 	if len(list) == 0 {
 		return s
 	}
+	for i, f := range list {
+		s = s.addOne(f, concat(index, i), indirect, multiples)
+	}
+	return s
+}
+
+func (s methodSet) addOne(f *Func, index []int, indirect bool, multiples bool) methodSet {
 	if s == nil {
 		s = make(methodSet)
 	}
-	for i, f := range list {
-		key := f.Id()
-		// if f is not in the set, add it
-		if !multiples {
-			// TODO(gri) A found method may not be added because it's not in the method set
-			// (!indirect && f.hasPtrRecv()). A 2nd method on the same level may be in the method
-			// set and may not collide with the first one, thus leading to a false positive.
-			// Is that possible? Investigate.
-			if _, found := s[key]; !found && (indirect || !f.hasPtrRecv()) {
-				s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect}
-				continue
-			}
+	key := f.Id()
+	// if f is not in the set, add it
+	if !multiples {
+		// TODO(gri) A found method may not be added because it's not in the method set
+		// (!indirect && f.hasPtrRecv()). A 2nd method on the same level may be in the method
+		// set and may not collide with the first one, thus leading to a false positive.
+		// Is that possible? Investigate.
+		if _, found := s[key]; !found && (indirect || !f.hasPtrRecv()) {
+			s[key] = &Selection{MethodVal, nil, f, index, indirect}
+			return s
 		}
-		s[key] = nil // collision
 	}
+	s[key] = nil // collision
 	return s
 }
diff --git a/src/go/types/named.go b/src/go/types/named.go
index f0c22d29e3..a9d1eab24b 100644
--- a/src/go/types/named.go
+++ b/src/go/types/named.go
@@ -18,10 +18,16 @@ type Named struct {
 	underlying Type           // possibly a *Named during setup; never a *Named once set up completely
 	tparams    *TypeParamList // type parameters, or nil
 	targs      *TypeList      // type arguments (after instantiation), or nil
-	methods    []*Func        // methods declared for this type (not the method set of this type); signatures are type-checked lazily
+
+	// methods declared for this type (not the method set of this type).
+	// Signatures are type-checked lazily.
+	// For non-instantiated types, this is a fully populated list of methods. For
+	// instantiated types, this is a 'lazy' list, and methods are instantiated
+	// when they are first accessed.
+	methods *methodList
 
 	// resolver may be provided to lazily resolve type parameters, underlying, and methods.
-	resolver func(*Context, *Named) (tparams *TypeParamList, underlying Type, methods []*Func)
+	resolver func(*Context, *Named) (tparams *TypeParamList, underlying Type, methods *methodList)
 	once     sync.Once // ensures that tparams, underlying, and methods are resolved before accessing
 }
 
@@ -32,7 +38,7 @@ func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
 	if _, ok := underlying.(*Named); ok {
 		panic("underlying type must not be *Named")
 	}
-	return (*Checker)(nil).newNamed(obj, nil, underlying, nil, methods)
+	return (*Checker)(nil).newNamed(obj, nil, underlying, nil, newMethodList(methods))
 }
 
 func (t *Named) resolve(ctxt *Context) *Named {
@@ -56,7 +62,7 @@ func (t *Named) resolve(ctxt *Context) *Named {
 }
 
 // newNamed is like NewNamed but with a *Checker receiver and additional orig argument.
-func (check *Checker) newNamed(obj *TypeName, orig *Named, underlying Type, tparams *TypeParamList, methods []*Func) *Named {
+func (check *Checker) newNamed(obj *TypeName, orig *Named, underlying Type, tparams *TypeParamList, methods *methodList) *Named {
 	typ := &Named{check: check, obj: obj, orig: orig, fromRHS: underlying, underlying: underlying, tparams: tparams, methods: methods}
 	if typ.orig == nil {
 		typ.orig = typ
@@ -99,10 +105,72 @@ func (t *Named) SetTypeParams(tparams []*TypeParam) {
 func (t *Named) TypeArgs() *TypeList { return t.targs }
 
 // NumMethods returns the number of explicit methods whose receiver is named type t.
-func (t *Named) NumMethods() int { return len(t.resolve(nil).methods) }
+func (t *Named) NumMethods() int { return t.resolve(nil).methods.Len() }
 
 // Method returns the i'th method of named type t for 0 <= i < t.NumMethods().
-func (t *Named) Method(i int) *Func { return t.resolve(nil).methods[i] }
+func (t *Named) Method(i int) *Func {
+	t.resolve(nil)
+	return t.methods.At(i, func() *Func {
+		return t.instantiateMethod(i)
+	})
+}
+
+// instiateMethod instantiates the i'th method for an instantiated receiver.
+func (t *Named) instantiateMethod(i int) *Func {
+	assert(t.TypeArgs().Len() > 0) // t must be an instance
+
+	// t.orig.methods is not lazy. origm is the method instantiated with its
+	// receiver type parameters (the "origin" method).
+	origm := t.orig.Method(i)
+	assert(origm != nil)
+
+	check := t.check
+	// Ensure that the original method is type-checked.
+	if check != nil {
+		check.objDecl(origm, nil)
+	}
+
+	origSig := origm.typ.(*Signature)
+	rbase, _ := deref(origSig.Recv().Type())
+
+	// If rbase is t, then origm is already the instantiated method we're looking
+	// for. In this case, we return origm to preserve the invariant that
+	// traversing Method->Receiver Type->Method should get back to the same
+	// method.
+	//
+	// This occurs if t is instantiated with the receiver type parameters, as in
+	// the use of m in func (r T[_]) m() { r.m() }.
+	if rbase == t {
+		return origm
+	}
+
+	sig := origSig
+	// We can only substitute if we have a correspondence between type arguments
+	// and type parameters. This check is necessary in the presence of invalid
+	// code.
+	if origSig.RecvTypeParams().Len() == t.targs.Len() {
+		ctxt := check.bestContext(nil)
+		smap := makeSubstMap(origSig.RecvTypeParams().list(), t.targs.list())
+		sig = check.subst(origm.pos, origSig, smap, ctxt).(*Signature)
+	}
+
+	if sig == origSig {
+		// No substitution occurred, but we still need to create a new signature to
+		// hold the instantiated receiver.
+		copy := *origSig
+		sig = &copy
+	}
+
+	var rtyp Type
+	if origm.hasPtrRecv() {
+		rtyp = NewPointer(t)
+	} else {
+		rtyp = t
+	}
+
+	sig.recv = NewParam(origSig.recv.pos, origSig.recv.pkg, origSig.recv.name, rtyp)
+	return NewFunc(origm.pos, origm.pkg, origm.name, sig)
+}
 
 // SetUnderlying sets the underlying type and marks t as complete.
 // t must not have type arguments.
@@ -125,9 +193,10 @@ func (t *Named) SetUnderlying(underlying Type) {
 func (t *Named) AddMethod(m *Func) {
 	assert(t.targs.Len() == 0)
 	t.resolve(nil)
-	if i, _ := lookupMethod(t.methods, m.pkg, m.name); i < 0 {
-		t.methods = append(t.methods, m)
+	if t.methods == nil {
+		t.methods = newMethodList(nil)
 	}
+	t.methods.Add(m)
 }
 
 func (t *Named) Underlying() Type { return t.resolve(nil).underlying }
@@ -230,6 +299,19 @@ func (n *Named) setUnderlying(typ Type) {
 	}
 }
 
+func (n *Named) lookupMethod(pkg *Package, name string) (int, *Func) {
+	n.resolve(nil)
+	// If n is an instance, we may not have yet instantiated all of its methods.
+	// Look up the method index in orig, and only instantiate method at the
+	// matching index (if any).
+	i, _ := n.orig.methods.Lookup(pkg, name)
+	if i < 0 {
+		return -1, nil
+	}
+	// For instances, m.Method(i) will be different from the orig method.
+	return i, n.Method(i)
+}
+
 // bestContext returns the best available context. In order of preference:
 // - the given ctxt, if non-nil
 // - check.ctxt, if check is non-nil
@@ -249,7 +331,7 @@ func (check *Checker) bestContext(ctxt *Context) *Context {
 
 // expandNamed ensures that the underlying type of n is instantiated.
 // The underlying type will be Typ[Invalid] if there was an error.
-func expandNamed(ctxt *Context, n *Named, instPos token.Pos) (tparams *TypeParamList, underlying Type, methods []*Func) {
+func expandNamed(ctxt *Context, n *Named, instPos token.Pos) (tparams *TypeParamList, underlying Type, methods *methodList) {
 	n.orig.resolve(ctxt)
 	assert(n.orig.underlying != nil)
 
@@ -271,80 +353,13 @@ func expandNamed(ctxt *Context, n *Named, instPos token.Pos) (tparams *TypeParam
 
 		smap := makeSubstMap(n.orig.tparams.list(), n.targs.list())
 		underlying = n.check.subst(instPos, n.orig.underlying, smap, ctxt)
-
-		for i := 0; i < n.orig.NumMethods(); i++ {
-			origm := n.orig.Method(i)
-
-			// During type checking origm may not have a fully set up type, so defer
-			// instantiation of its signature until later.
-			m := NewFunc(origm.pos, origm.pkg, origm.name, nil)
-			m.hasPtrRecv_ = origm.hasPtrRecv()
-			// Setting instRecv here allows us to complete later (we need the
-			// instRecv to get targs and the original method).
-			m.instRecv = n
-
-			methods = append(methods, m)
-		}
 	} else {
 		underlying = Typ[Invalid]
 	}
 
-	// Methods should not escape the type checker API without being completed. If
-	// we're in the context of a type checking pass, we need to defer this until
-	// later (not all methods may have types).
-	completeMethods := func() {
-		for _, m := range methods {
-			if m.instRecv != nil {
-				check.completeMethod(ctxt, m)
-			}
-		}
-	}
-	if check != nil {
-		check.later(completeMethods)
-	} else {
-		completeMethods()
-	}
-
-	return n.orig.tparams, underlying, methods
-}
-
-func (check *Checker) completeMethod(ctxt *Context, m *Func) {
-	assert(m.instRecv != nil)
-	rbase := m.instRecv
-	m.instRecv = nil
-	m.setColor(black)
-
-	assert(rbase.TypeArgs().Len() > 0)
-
-	// Look up the original method.
-	_, orig := lookupMethod(rbase.orig.methods, rbase.obj.pkg, m.name)
-	assert(orig != nil)
-	if check != nil {
-		check.objDecl(orig, nil)
-	}
-	origSig := orig.typ.(*Signature)
-	if origSig.RecvTypeParams().Len() != rbase.targs.Len() {
-		m.typ = origSig // or new(Signature), but we can't use Typ[Invalid]: Funcs must have Signature type
-		return          // error reported elsewhere
-	}
-
-	smap := makeSubstMap(origSig.RecvTypeParams().list(), rbase.targs.list())
-	sig := check.subst(orig.pos, origSig, smap, ctxt).(*Signature)
-	if sig == origSig {
-		// No substitution occurred, but we still need to create a new signature to
-		// hold the instantiated receiver.
-		copy := *origSig
-		sig = &copy
-	}
-	var rtyp Type
-	if m.hasPtrRecv() {
-		rtyp = NewPointer(rbase)
-	} else {
-		rtyp = rbase
-	}
-	sig.recv = NewParam(origSig.recv.pos, origSig.recv.pkg, origSig.recv.name, rtyp)
+	mlist := newLazyMethodList(n.orig.methods.Len())
 
-	m.typ = sig
+	return n.orig.tparams, underlying, mlist
 }
 
 // safeUnderlying returns the underlying of typ without expanding instances, to
diff --git a/src/go/types/object.go b/src/go/types/object.go
index cf05384a87..fb377002aa 100644
--- a/src/go/types/object.go
+++ b/src/go/types/object.go
@@ -235,7 +235,7 @@ func NewTypeName(pos token.Pos, pkg *Package, name string, typ Type) *TypeName {
 func _NewTypeNameLazy(pos token.Pos, pkg *Package, name string, load func(named *Named) (tparams []*TypeParam, underlying Type, methods []*Func)) *TypeName {
 	obj := NewTypeName(pos, pkg, name, nil)
 
-	resolve := func(_ *Context, t *Named) (*TypeParamList, Type, []*Func) {
+	resolve := func(_ *Context, t *Named) (*TypeParamList, Type, *methodList) {
 		tparams, underlying, methods := load(t)
 
 		switch underlying.(type) {
@@ -243,7 +243,7 @@ func _NewTypeNameLazy(pos token.Pos, pkg *Package, name string, load func(named
 			panic(fmt.Sprintf("invalid underlying type %T", t.underlying))
 		}
 
-		return bindTParams(tparams), underlying, methods
+		return bindTParams(tparams), underlying, newMethodList(methods)
 	}
 
 	NewNamed(obj, nil, nil).resolver = resolve
@@ -319,8 +319,7 @@ func (*Var) isDependency() {} // a variable may be a dependency of an initializa
 // An abstract method may belong to many interfaces due to embedding.
 type Func struct {
 	object
-	instRecv    *Named // if non-nil, the receiver type for an incomplete instance method
-	hasPtrRecv_ bool   // only valid for methods that don't have a type yet; use hasPtrRecv() to read
+	hasPtrRecv_ bool // only valid for methods that don't have a type yet; use hasPtrRecv() to read
 }
 
 // NewFunc returns a new function with the given signature, representing
@@ -331,7 +330,7 @@ func NewFunc(pos token.Pos, pkg *Package, name string, sig *Signature) *Func {
 	if sig != nil {
 		typ = sig
 	}
-	return &Func{object{nil, pos, pkg, name, typ, 0, colorFor(typ), token.NoPos}, nil, false}
+	return &Func{object{nil, pos, pkg, name, typ, 0, colorFor(typ), token.NoPos}, false}
 }
 
 // FullName returns the package- or receiver-type-qualified name of
diff --git a/src/go/types/sizeof_test.go b/src/go/types/sizeof_test.go
index b78099d0d0..bfd14a8109 100644
--- a/src/go/types/sizeof_test.go
+++ b/src/go/types/sizeof_test.go
@@ -30,7 +30,7 @@ func TestSizeof(t *testing.T) {
 		{Interface{}, 44, 88},
 		{Map{}, 16, 32},
 		{Chan{}, 12, 24},
-		{Named{}, 64, 120},
+		{Named{}, 56, 104},
 		{TypeParam{}, 28, 48},
 		{term{}, 12, 24},
 
@@ -39,7 +39,7 @@ func TestSizeof(t *testing.T) {
 		{Const{}, 48, 88},
 		{TypeName{}, 40, 72},
 		{Var{}, 44, 80},
-		{Func{}, 48, 88},
+		{Func{}, 44, 80},
 		{Label{}, 44, 80},
 		{Builtin{}, 44, 80},
 		{Nil{}, 40, 72},
diff --git a/src/go/types/typexpr.go b/src/go/types/typexpr.go
index 52966bb047..00c250b5b6 100644
--- a/src/go/types/typexpr.go
+++ b/src/go/types/typexpr.go
@@ -437,7 +437,7 @@ func (check *Checker) instantiatedType(ix *typeparams.IndexExpr, def *Named) (re
 	}
 	def.setUnderlying(inst)
 
-	inst.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, []*Func) {
+	inst.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, *methodList) {
 		tparams := orig.TypeParams().list()
 
 		inferred := targs