go/ssa: simplify TypesWithMethodSets

Details:
- rename (*Program).TypesWithMethodSets() to RuntimeTypes()
- delete (*Package).TypesWithMethodSets() method and simplify
- move code to methods.go
- update test to use

1-2% improvement in space and time (though I barely trust this data
because the GC at tip is in such terrible state).

Change-Id: I38eab78b11e0ad0ff16e0530e775b6ff6a2ab246
Reviewed-on: https://go-review.googlesource.com/3148
Reviewed-by: Robert Griesemer <gri@golang.org>

7 files changed, 145 insertions, 227 deletions

diff --git a/go/pointer/gen.go b/go/pointer/gen.go
index 48ca368..6c256ac 100644
--- a/go/pointer/gen.go
+++ b/go/pointer/gen.go
@@ -1262,7 +1262,7 @@ func (a *analysis) generate() {
 
 	// Create nodes and constraints for all methods of all types
 	// that are dynamically accessible via reflection or interfaces.
-	for _, T := range a.prog.TypesWithMethodSets() {
+	for _, T := range a.prog.RuntimeTypes() {
 		a.genMethodsOf(T)
 	}
 
diff --git a/go/ssa/builder.go b/go/ssa/builder.go
index 93755d0..3e70a85 100644
--- a/go/ssa/builder.go
+++ b/go/ssa/builder.go
@@ -2193,7 +2193,7 @@ func (p *Package) Build() {
 	// that would require package creation in topological order.
 	for name, mem := range p.Members {
 		if ast.IsExported(name) {
-			p.needMethodsOf(mem.Type())
+			p.Prog.needMethodsOf(mem.Type())
 		}
 	}
 	if p.Prog.mode&LogSource != 0 {
@@ -2301,129 +2301,3 @@ func (p *Package) typeOf(e ast.Expr) types.Type {
 	panic(fmt.Sprintf("no type for %T @ %s",
 		e, p.Prog.Fset.Position(e.Pos())))
 }
-
-// needMethodsOf ensures that runtime type information (including the
-// complete method set) is available for the specified type T and all
-// its subcomponents.
-//
-// needMethodsOf must be called for at least every type that is an
-// operand of some MakeInterface instruction, and for the type of
-// every exported package member.
-//
-// Precondition: T is not a method signature (*Signature with Recv()!=nil).
-//
-// Thread-safe.  (Called via emitConv from multiple builder goroutines.)
-//
-// TODO(adonovan): make this faster.  It accounts for 20% of SSA build
-// time.  Do we need to maintain a distinct needRTTI and methodSets per
-// package?  Using just one in the program might be much faster.
-//
-func (p *Package) needMethodsOf(T types.Type) {
-	p.methodsMu.Lock()
-	p.needMethods(T, false)
-	p.methodsMu.Unlock()
-}
-
-// Precondition: T is not a method signature (*Signature with Recv()!=nil).
-// Precondition: the p.methodsMu lock is held.
-// Recursive case: skip => don't call makeMethods(T).
-func (p *Package) needMethods(T types.Type, skip bool) {
-	// Each package maintains its own set of types it has visited.
-	if prevSkip, ok := p.needRTTI.At(T).(bool); ok {
-		// needMethods(T) was previously called
-		if !prevSkip || skip {
-			return // already seen, with same or false 'skip' value
-		}
-	}
-	p.needRTTI.Set(T, skip)
-
-	// Prune the recursion if we find a named or *named type
-	// belonging to another package.
-	var n *types.Named
-	switch T := T.(type) {
-	case *types.Named:
-		n = T
-	case *types.Pointer:
-		n, _ = T.Elem().(*types.Named)
-	}
-	if n != nil {
-		owner := n.Obj().Pkg()
-		if owner == nil {
-			return // built-in error type
-		}
-		if owner != p.Object {
-			return // belongs to another package
-		}
-	}
-
-	// All the actual method sets live in the Program so that
-	// multiple packages can share a single copy in memory of the
-	// symbols that would be compiled into multiple packages (as
-	// weak symbols).
-	if !skip && p.Prog.makeMethods(T) {
-		p.methodSets = append(p.methodSets, T)
-	}
-
-	// Recursion over signatures of each method.
-	tmset := p.Prog.MethodSets.MethodSet(T)
-	for i := 0; i < tmset.Len(); i++ {
-		sig := tmset.At(i).Type().(*types.Signature)
-		p.needMethods(sig.Params(), false)
-		p.needMethods(sig.Results(), false)
-	}
-
-	switch t := T.(type) {
-	case *types.Basic:
-		// nop
-
-	case *types.Interface:
-		// nop---handled by recursion over method set.
-
-	case *types.Pointer:
-		p.needMethods(t.Elem(), false)
-
-	case *types.Slice:
-		p.needMethods(t.Elem(), false)
-
-	case *types.Chan:
-		p.needMethods(t.Elem(), false)
-
-	case *types.Map:
-		p.needMethods(t.Key(), false)
-		p.needMethods(t.Elem(), false)
-
-	case *types.Signature:
-		if t.Recv() != nil {
-			panic(fmt.Sprintf("Signature %s has Recv %s", t, t.Recv()))
-		}
-		p.needMethods(t.Params(), false)
-		p.needMethods(t.Results(), false)
-
-	case *types.Named:
-		// A pointer-to-named type can be derived from a named
-		// type via reflection.  It may have methods too.
-		p.needMethods(types.NewPointer(T), false)
-
-		// Consider 'type T struct{S}' where S has methods.
-		// Reflection provides no way to get from T to struct{S},
-		// only to S, so the method set of struct{S} is unwanted,
-		// so set 'skip' flag during recursion.
-		p.needMethods(t.Underlying(), true)
-
-	case *types.Array:
-		p.needMethods(t.Elem(), false)
-
-	case *types.Struct:
-		for i, n := 0, t.NumFields(); i < n; i++ {
-			p.needMethods(t.Field(i).Type(), false)
-		}
-
-	case *types.Tuple:
-		for i, n := 0, t.Len(); i < n; i++ {
-			p.needMethods(t.At(i).Type(), false)
-		}
-
-	default:
-		panic(T)
-	}
-}
diff --git a/go/ssa/builder_test.go b/go/ssa/builder_test.go
index bda9ac6..dc7434f 100644
--- a/go/ssa/builder_test.go
+++ b/go/ssa/builder_test.go
@@ -151,8 +151,8 @@ func main() {
 	}
 }
 
-// TestTypesWithMethodSets tests that Package.TypesWithMethodSets includes all necessary types.
-func TestTypesWithMethodSets(t *testing.T) {
+// TestRuntimeTypes tests that (*Program).RuntimeTypes() includes all necessary types.
+func TestRuntimeTypes(t *testing.T) {
 	tests := []struct {
 		input string
 		want  []string
@@ -167,7 +167,7 @@ func TestTypesWithMethodSets(t *testing.T) {
 		},
 		// Subcomponents of type of exported package-level var are needed.
 		{`package C; import "bytes"; var V struct {*bytes.Buffer}`,
-			[]string{"*struct{*bytes.Buffer}", "struct{*bytes.Buffer}"},
+			[]string{"*bytes.Buffer", "*struct{*bytes.Buffer}", "struct{*bytes.Buffer}"},
 		},
 		// Subcomponents of type of unexported package-level var are not needed.
 		{`package D; import "bytes"; var v struct {*bytes.Buffer}`,
@@ -175,7 +175,7 @@ func TestTypesWithMethodSets(t *testing.T) {
 		},
 		// Subcomponents of type of exported package-level function are needed.
 		{`package E; import "bytes"; func F(struct {*bytes.Buffer}) {}`,
-			[]string{"struct{*bytes.Buffer}"},
+			[]string{"*bytes.Buffer", "struct{*bytes.Buffer}"},
 		},
 		// Subcomponents of type of unexported package-level function are not needed.
 		{`package F; import "bytes"; func f(struct {*bytes.Buffer}) {}`,
@@ -187,11 +187,11 @@ func TestTypesWithMethodSets(t *testing.T) {
 		},
 		// ...unless used by MakeInterface.
 		{`package G2; import "bytes"; type x struct{}; func (x) G(struct {*bytes.Buffer}) {}; var v interface{} = x{}`,
-			[]string{"*p.x", "p.x", "struct{*bytes.Buffer}"},
+			[]string{"*bytes.Buffer", "*p.x", "p.x", "struct{*bytes.Buffer}"},
 		},
 		// Subcomponents of type of unexported method are not needed.
 		{`package I; import "bytes"; type X struct{}; func (X) G(struct {*bytes.Buffer}) {}`,
-			[]string{"*p.X", "p.X", "struct{*bytes.Buffer}"},
+			[]string{"*bytes.Buffer", "*p.X", "p.X", "struct{*bytes.Buffer}"},
 		},
 		// Local types aren't needed.
 		{`package J; import "bytes"; func f() { type T struct {*bytes.Buffer}; var t T; _ = t }`,
@@ -199,11 +199,11 @@ func TestTypesWithMethodSets(t *testing.T) {
 		},
 		// ...unless used by MakeInterface.
 		{`package K; import "bytes"; func f() { type T struct {*bytes.Buffer}; _ = interface{}(T{}) }`,
-			[]string{"*p.T", "p.T"},
+			[]string{"*bytes.Buffer", "*p.T", "p.T"},
 		},
 		// Types used as operand of MakeInterface are needed.
 		{`package L; import "bytes"; func f() { _ = interface{}(struct{*bytes.Buffer}{}) }`,
-			[]string{"struct{*bytes.Buffer}"},
+			[]string{"*bytes.Buffer", "struct{*bytes.Buffer}"},
 		},
 		// MakeInterface is optimized away when storing to a blank.
 		{`package M; import "bytes"; var _ interface{} = struct{*bytes.Buffer}{}`,
@@ -226,17 +226,17 @@ func TestTypesWithMethodSets(t *testing.T) {
 			continue
 		}
 		prog := ssa.Create(iprog, ssa.SanityCheckFunctions)
-		mainPkg := prog.Package(iprog.Created[0].Pkg)
 		prog.BuildAll()
 
 		var typstrs []string
-		for _, T := range mainPkg.TypesWithMethodSets() {
+		for _, T := range prog.RuntimeTypes() {
 			typstrs = append(typstrs, T.String())
 		}
 		sort.Strings(typstrs)
 
 		if !reflect.DeepEqual(typstrs, test.want) {
-			t.Errorf("test 'package %s': got %q, want %q", f.Name.Name, typstrs, test.want)
+			t.Errorf("test 'package %s': got %q, want %q",
+				f.Name.Name, typstrs, test.want)
 		}
 	}
 }
diff --git a/go/ssa/emit.go b/go/ssa/emit.go
index 261d6e0..f1ba0f7 100644
--- a/go/ssa/emit.go
+++ b/go/ssa/emit.go
@@ -208,7 +208,7 @@ func emitConv(f *Function, val Value, typ types.Type) Value {
 			val = emitConv(f, val, DefaultType(ut_src))
 		}
 
-		f.Pkg.needMethodsOf(val.Type())
+		f.Pkg.Prog.needMethodsOf(val.Type())
 		mi := &MakeInterface{X: val}
 		mi.setType(typ)
 		return f.emit(mi)
diff --git a/go/ssa/methods.go b/go/ssa/methods.go
index 1ef725c..12534de 100644
--- a/go/ssa/methods.go
+++ b/go/ssa/methods.go
@@ -55,44 +55,6 @@ func (prog *Program) LookupMethod(T types.Type, pkg *types.Package, name string)
 	return prog.Method(sel)
 }
 
-// makeMethods ensures that all concrete methods of type T are
-// generated.  It is equivalent to calling prog.Method() on all
-// members of T.methodSet(), but acquires fewer locks.
-//
-// It reports whether the type's (concrete) method set is non-empty.
-//
-// Thread-safe.
-//
-// EXCLUSIVE_LOCKS_ACQUIRED(prog.methodsMu)
-//
-func (prog *Program) makeMethods(T types.Type) bool {
-	if isInterface(T) {
-		return false // abstract method
-	}
-	tmset := prog.MethodSets.MethodSet(T)
-	n := tmset.Len()
-	if n == 0 {
-		return false // empty (common case)
-	}
-
-	if prog.mode&LogSource != 0 {
-		defer logStack("makeMethods %s", T)()
-	}
-
-	prog.methodsMu.Lock()
-	defer prog.methodsMu.Unlock()
-
-	mset := prog.createMethodSet(T)
-	if !mset.complete {
-		mset.complete = true
-		for i := 0; i < n; i++ {
-			prog.addMethod(mset, tmset.At(i))
-		}
-	}
-
-	return true
-}
-
 // methodSet contains the (concrete) methods of a non-interface type.
 type methodSet struct {
 	mapping  map[string]*Function // populated lazily
@@ -135,18 +97,15 @@ func (prog *Program) addMethod(mset *methodSet, sel *types.Selection) *Function
 	return fn
 }
 
-// TypesWithMethodSets returns a new unordered slice containing all
+// RuntimeTypes returns a new unordered slice containing all
 // concrete types in the program for which a complete (non-empty)
 // method set is required at run-time.
 //
-// It is the union of pkg.TypesWithMethodSets() for all pkg in
-// prog.AllPackages().
-//
 // Thread-safe.
 //
 // EXCLUSIVE_LOCKS_ACQUIRED(prog.methodsMu)
 //
-func (prog *Program) TypesWithMethodSets() []types.Type {
+func (prog *Program) RuntimeTypes() []types.Type {
 	prog.methodsMu.Lock()
 	defer prog.methodsMu.Unlock()
 
@@ -159,39 +118,126 @@ func (prog *Program) TypesWithMethodSets() []types.Type {
 	return res
 }
 
-// TypesWithMethodSets returns an unordered slice containing the set
-// of all concrete types referenced within package pkg and not
-// belonging to some other package, for which a complete (non-empty)
-// method set is required at run-time.
+// declaredFunc returns the concrete function/method denoted by obj.
+// Panic ensues if there is none.
+//
+func (prog *Program) declaredFunc(obj *types.Func) *Function {
+	if v := prog.packageLevelValue(obj); v != nil {
+		return v.(*Function)
+	}
+	panic("no concrete method: " + obj.String())
+}
+
+// needMethodsOf ensures that runtime type information (including the
+// complete method set) is available for the specified type T and all
+// its subcomponents.
+//
+// needMethodsOf must be called for at least every type that is an
+// operand of some MakeInterface instruction, and for the type of
+// every exported package member.
 //
-// A type belongs to a package if it is a named type or a pointer to a
-// named type, and the name was defined in that package.  All other
-// types belong to no package.
+// Precondition: T is not a method signature (*Signature with Recv()!=nil).
 //
-// A type may appear in the TypesWithMethodSets() set of multiple
-// distinct packages if that type belongs to no package.  Typical
-// compilers emit method sets for such types multiple times (using
-// weak symbols) into each package that references them, with the
-// linker performing duplicate elimination.
+// Thread-safe.  (Called via emitConv from multiple builder goroutines.)
 //
-// This set includes the types of all operands of some MakeInterface
-// instruction, the types of all exported members of some package, and
-// all types that are subcomponents, since even types that aren't used
-// directly may be derived via reflection.
+// TODO(adonovan): make this faster.  It accounts for 20% of SSA build time.
 //
-// Callers must not mutate the result.
+// EXCLUSIVE_LOCKS_ACQUIRED(prog.methodsMu)
 //
-func (pkg *Package) TypesWithMethodSets() []types.Type {
-	// pkg.methodsMu not required; concurrent (build) phase is over.
-	return pkg.methodSets
+func (prog *Program) needMethodsOf(T types.Type) {
+	prog.methodsMu.Lock()
+	prog.needMethods(T, false)
+	prog.methodsMu.Unlock()
 }
 
-// declaredFunc returns the concrete function/method denoted by obj.
-// Panic ensues if there is none.
+// Precondition: T is not a method signature (*Signature with Recv()!=nil).
+// Recursive case: skip => don't create methods for T.
 //
-func (prog *Program) declaredFunc(obj *types.Func) *Function {
-	if v := prog.packageLevelValue(obj); v != nil {
-		return v.(*Function)
+// EXCLUSIVE_LOCKS_REQUIRED(prog.methodsMu)
+//
+func (prog *Program) needMethods(T types.Type, skip bool) {
+	// Each package maintains its own set of types it has visited.
+	if prevSkip, ok := prog.runtimeTypes.At(T).(bool); ok {
+		// needMethods(T) was previously called
+		if !prevSkip || skip {
+			return // already seen, with same or false 'skip' value
+		}
+	}
+	prog.runtimeTypes.Set(T, skip)
+
+	tmset := prog.MethodSets.MethodSet(T)
+
+	if !skip && !isInterface(T) && tmset.Len() > 0 {
+		// Create methods of T.
+		mset := prog.createMethodSet(T)
+		if !mset.complete {
+			mset.complete = true
+			n := tmset.Len()
+			for i := 0; i < n; i++ {
+				prog.addMethod(mset, tmset.At(i))
+			}
+		}
+	}
+
+	// Recursion over signatures of each method.
+	for i := 0; i < tmset.Len(); i++ {
+		sig := tmset.At(i).Type().(*types.Signature)
+		prog.needMethods(sig.Params(), false)
+		prog.needMethods(sig.Results(), false)
+	}
+
+	switch t := T.(type) {
+	case *types.Basic:
+		// nop
+
+	case *types.Interface:
+		// nop---handled by recursion over method set.
+
+	case *types.Pointer:
+		prog.needMethods(t.Elem(), false)
+
+	case *types.Slice:
+		prog.needMethods(t.Elem(), false)
+
+	case *types.Chan:
+		prog.needMethods(t.Elem(), false)
+
+	case *types.Map:
+		prog.needMethods(t.Key(), false)
+		prog.needMethods(t.Elem(), false)
+
+	case *types.Signature:
+		if t.Recv() != nil {
+			panic(fmt.Sprintf("Signature %s has Recv %s", t, t.Recv()))
+		}
+		prog.needMethods(t.Params(), false)
+		prog.needMethods(t.Results(), false)
+
+	case *types.Named:
+		// A pointer-to-named type can be derived from a named
+		// type via reflection.  It may have methods too.
+		prog.needMethods(types.NewPointer(T), false)
+
+		// Consider 'type T struct{S}' where S has methods.
+		// Reflection provides no way to get from T to struct{S},
+		// only to S, so the method set of struct{S} is unwanted,
+		// so set 'skip' flag during recursion.
+		prog.needMethods(t.Underlying(), true)
+
+	case *types.Array:
+		prog.needMethods(t.Elem(), false)
+
+	case *types.Struct:
+		for i, n := 0, t.NumFields(); i < n; i++ {
+			prog.needMethods(t.Field(i).Type(), false)
+		}
+
+	case *types.Tuple:
+		for i, n := 0, t.Len(); i < n; i++ {
+			prog.needMethods(t.At(i).Type(), false)
+		}
+
+	default:
+		panic(T)
 	}
-	panic("no concrete method: " + obj.String())
 }
diff --git a/go/ssa/ssa.go b/go/ssa/ssa.go
index 406611e..ac46f27 100644
--- a/go/ssa/ssa.go
+++ b/go/ssa/ssa.go
@@ -28,11 +28,12 @@ type Program struct {
 	mode       BuilderMode                 // set of mode bits for SSA construction
 	MethodSets types.MethodSetCache        // cache of type-checker's method-sets
 
-	methodsMu  sync.Mutex                 // guards the following maps:
-	methodSets typeutil.Map               // maps type to its concrete methodSet
-	canon      typeutil.Map               // type canonicalization map
-	bounds     map[*types.Func]*Function  // bounds for curried x.Method closures
-	thunks     map[selectionKey]*Function // thunks for T.Method expressions
+	methodsMu    sync.Mutex                 // guards the following maps:
+	methodSets   typeutil.Map               // maps type to its concrete methodSet
+	runtimeTypes typeutil.Map               // types for which rtypes are needed
+	canon        typeutil.Map               // type canonicalization map
+	bounds       map[*types.Func]*Function  // bounds for curried x.Method closures
+	thunks       map[selectionKey]*Function // thunks for T.Method expressions
 }
 
 // A Package is a single analyzed Go package containing Members for
@@ -41,21 +42,18 @@ type Program struct {
 // type-specific accessor methods Func, Type, Var and Const.
 //
 type Package struct {
-	Prog       *Program               // the owning program
-	Object     *types.Package         // the type checker's package object for this package
-	Members    map[string]Member      // all package members keyed by name
-	methodsMu  sync.Mutex             // guards needRTTI and methodSets
-	methodSets []types.Type           // types whose method sets are included in this package
-	values     map[types.Object]Value // package members (incl. types and methods), keyed by object
-	init       *Function              // Func("init"); the package's init function
-	debug      bool                   // include full debug info in this package.
+	Prog    *Program               // the owning program
+	Object  *types.Package         // the type checker's package object for this package
+	Members map[string]Member      // all package members keyed by name
+	values  map[types.Object]Value // package members (incl. types and methods), keyed by object
+	init    *Function              // Func("init"); the package's init function
+	debug   bool                   // include full debug info in this package.
 
 	// The following fields are set transiently, then cleared
 	// after building.
-	started  int32               // atomically tested and set at start of build phase
-	ninit    int32               // number of init functions
-	info     *loader.PackageInfo // package ASTs and type information
-	needRTTI typeutil.Map        // types for which runtime type info is needed
+	started int32               // atomically tested and set at start of build phase
+	ninit   int32               // number of init functions
+	info    *loader.PackageInfo // package ASTs and type information
 }
 
 // A Member is a member of a Go package, implemented by *NamedConst,
diff --git a/go/ssa/ssautil/visit.go b/go/ssa/ssautil/visit.go
index 14de154..30843c3 100644
--- a/go/ssa/ssautil/visit.go
+++ b/go/ssa/ssautil/visit.go
@@ -41,7 +41,7 @@ func (visit *visitor) program() {
 			}
 		}
 	}
-	for _, T := range visit.prog.TypesWithMethodSets() {
+	for _, T := range visit.prog.RuntimeTypes() {
 		mset := visit.prog.MethodSets.MethodSet(T)
 		for i, n := 0, mset.Len(); i < n; i++ {
 			visit.function(visit.prog.Method(mset.At(i)))