go/ssa: monomorphize generic instantiations.

Monomorphize the instantiation of generic functions. Applies type
substitution while building the function instantiation.

Adds a new BuilderMode, ssa.InstantiateGenerics, to enable
monomorphization. InstantiateGenerics is turned on by the flag 'G' in
tools that specify the BuilderMode.

Adds a parameterized field to Program to detect when a MethodValue is
parameterized.

Thunk creation creates new MethodExpr selections. Adds a new methodExpr
type to construct a MethodExpr from outside of types, and selection
interface to generalize a *methodExpr and *types.Selection.

Tests x/tools/go/ssa/interp against the runnable examples in
$GOROOT/test/typeparam/*.go. Some additional models to support files.

Misc. cleanup:
- adding (*canonizer).instantiateMethod to create a canonical
  representative of a method.
- documenting builder.go
- adding (*subster).types that applies type substitution to a list.

Updates golang/go#48525

Change-Id: I885a4223900feaa3664e35caf8618d11ba16a2a7
Reviewed-on: https://go-review.googlesource.com/c/tools/+/356315
Reviewed-by: Dominik Honnef <dominik@honnef.co>
Reviewed-by: Robert Findley <rfindley@google.com>
Reviewed-by: Zvonimir Pavlinovic <zpavlinovic@google.com>
Run-TryBot: Tim King <taking@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>

1 files changed, 86 insertions, 78 deletions

diff --git a/go/ssa/builder_test.go b/go/ssa/builder_test.go
index 3fd9a8ae2..6b9c79803 100644
--- a/go/ssa/builder_test.go
+++ b/go/ssa/builder_test.go
@@ -42,7 +42,7 @@ import (
 
 func main() {
         var t testing.T
-	t.Parallel()    // static call to external declared method
+	    t.Parallel()    // static call to external declared method
         t.Fail()        // static call to promoted external declared method
         testing.Short() // static call to external package-level function
 
@@ -61,8 +61,9 @@ func main() {
 
 	// Build an SSA program from the parsed file.
 	// Load its dependencies from gc binary export data.
+	mode := ssa.SanityCheckFunctions
 	mainPkg, _, err := ssautil.BuildPackage(&types.Config{Importer: importer.Default()}, fset,
-		types.NewPackage("main", ""), []*ast.File{f}, ssa.SanityCheckFunctions)
+		types.NewPackage("main", ""), []*ast.File{f}, mode)
 	if err != nil {
 		t.Error(err)
 		return
@@ -230,8 +231,9 @@ func TestRuntimeTypes(t *testing.T) {
 
 		// Create a single-file main package.
 		// Load dependencies from gc binary export data.
+		mode := ssa.SanityCheckFunctions
 		ssapkg, _, err := ssautil.BuildPackage(&types.Config{Importer: importer.Default()}, fset,
-			types.NewPackage("p", ""), []*ast.File{f}, ssa.SanityCheckFunctions)
+			types.NewPackage("p", ""), []*ast.File{f}, mode)
 		if err != nil {
 			t.Errorf("test %q: %s", test.input[:15], err)
 			continue
@@ -378,7 +380,7 @@ var (
 	}
 
 	// Create and build SSA
-	prog := ssautil.CreateProgram(lprog, 0)
+	prog := ssautil.CreateProgram(lprog, ssa.BuilderMode(0))
 	prog.Build()
 
 	// Enumerate reachable synthetic functions
@@ -484,7 +486,7 @@ func h(error)
 	}
 
 	// Create and build SSA
-	prog := ssautil.CreateProgram(lprog, 0)
+	prog := ssautil.CreateProgram(lprog, ssa.BuilderMode(0))
 	p := prog.Package(lprog.Package("p").Pkg)
 	p.Build()
 	g := p.Func("g")
@@ -553,7 +555,7 @@ func LoadPointer(addr *unsafe.Pointer) (val unsafe.Pointer)
 	}
 
 	// Create and build SSA
-	prog := ssautil.CreateProgram(lprog, 0)
+	prog := ssautil.CreateProgram(lprog, ssa.BuilderMode(0))
 	p := prog.Package(lprog.Package("p").Pkg)
 	p.Build()
 
@@ -608,83 +610,85 @@ var indirect = R[int].M
 		t.Fatalf("Load: %v", err)
 	}
 
-	// Create and build SSA
-	prog := ssautil.CreateProgram(lprog, 0)
-	p := prog.Package(lprog.Package("p").Pkg)
-	p.Build()
-
-	for _, entry := range []struct {
-		name    string // name of the package variable
-		typ     string // type of the package variable
-		wrapper string // wrapper function to which the package variable is set
-		callee  string // callee within the wrapper function
-	}{
-		{
-			"bound",
-			"*func() int",
-			"(p.S[int]).M$bound",
-			"(p.S[int]).M[[int]]",
-		},
-		{
-			"thunk",
-			"*func(p.S[int]) int",
-			"(p.S[int]).M$thunk",
-			"(p.S[int]).M[[int]]",
-		},
-		{
-			"indirect",
-			"*func(p.R[int]) int",
-			"(p.R[int]).M$thunk",
-			"(p.S[int]).M[[int]]",
-		},
-	} {
-		entry := entry
-		t.Run(entry.name, func(t *testing.T) {
-			v := p.Var(entry.name)
-			if v == nil {
-				t.Fatalf("Did not find variable for %q in %s", entry.name, p.String())
-			}
-			if v.Type().String() != entry.typ {
-				t.Errorf("Expected type for variable %s: %q. got %q", v, entry.typ, v.Type())
-			}
+	for _, mode := range []ssa.BuilderMode{ssa.BuilderMode(0), ssa.InstantiateGenerics} {
+		// Create and build SSA
+		prog := ssautil.CreateProgram(lprog, mode)
+		p := prog.Package(lprog.Package("p").Pkg)
+		p.Build()
+
+		for _, entry := range []struct {
+			name    string // name of the package variable
+			typ     string // type of the package variable
+			wrapper string // wrapper function to which the package variable is set
+			callee  string // callee within the wrapper function
+		}{
+			{
+				"bound",
+				"*func() int",
+				"(p.S[int]).M$bound",
+				"(p.S[int]).M[[int]]",
+			},
+			{
+				"thunk",
+				"*func(p.S[int]) int",
+				"(p.S[int]).M$thunk",
+				"(p.S[int]).M[[int]]",
+			},
+			{
+				"indirect",
+				"*func(p.R[int]) int",
+				"(p.R[int]).M$thunk",
+				"(p.S[int]).M[[int]]",
+			},
+		} {
+			entry := entry
+			t.Run(entry.name, func(t *testing.T) {
+				v := p.Var(entry.name)
+				if v == nil {
+					t.Fatalf("Did not find variable for %q in %s", entry.name, p.String())
+				}
+				if v.Type().String() != entry.typ {
+					t.Errorf("Expected type for variable %s: %q. got %q", v, entry.typ, v.Type())
+				}
 
-			// Find the wrapper for v. This is stored exactly once in init.
-			var wrapper *ssa.Function
-			for _, bb := range p.Func("init").Blocks {
-				for _, i := range bb.Instrs {
-					if store, ok := i.(*ssa.Store); ok && v == store.Addr {
-						switch val := store.Val.(type) {
-						case *ssa.Function:
-							wrapper = val
-						case *ssa.MakeClosure:
-							wrapper = val.Fn.(*ssa.Function)
+				// Find the wrapper for v. This is stored exactly once in init.
+				var wrapper *ssa.Function
+				for _, bb := range p.Func("init").Blocks {
+					for _, i := range bb.Instrs {
+						if store, ok := i.(*ssa.Store); ok && v == store.Addr {
+							switch val := store.Val.(type) {
+							case *ssa.Function:
+								wrapper = val
+							case *ssa.MakeClosure:
+								wrapper = val.Fn.(*ssa.Function)
+							}
 						}
 					}
 				}
-			}
-			if wrapper == nil {
-				t.Fatalf("failed to find wrapper function for %s", entry.name)
-			}
-			if wrapper.String() != entry.wrapper {
-				t.Errorf("Expected wrapper function %q. got %q", wrapper, entry.wrapper)
-			}
+				if wrapper == nil {
+					t.Fatalf("failed to find wrapper function for %s", entry.name)
+				}
+				if wrapper.String() != entry.wrapper {
+					t.Errorf("Expected wrapper function %q. got %q", wrapper, entry.wrapper)
+				}
 
-			// Find the callee within the wrapper. There should be exactly one call.
-			var callee *ssa.Function
-			for _, bb := range wrapper.Blocks {
-				for _, i := range bb.Instrs {
-					if call, ok := i.(*ssa.Call); ok {
-						callee = call.Call.StaticCallee()
+				// Find the callee within the wrapper. There should be exactly one call.
+				var callee *ssa.Function
+				for _, bb := range wrapper.Blocks {
+					for _, i := range bb.Instrs {
+						if call, ok := i.(*ssa.Call); ok {
+							callee = call.Call.StaticCallee()
+						}
 					}
 				}
-			}
-			if callee == nil {
-				t.Fatalf("failed to find callee within wrapper %s", wrapper)
-			}
-			if callee.String() != entry.callee {
-				t.Errorf("Expected callee in wrapper %q is %q. got %q", v, entry.callee, callee)
-			}
-		})
+				if callee == nil {
+					t.Fatalf("failed to find callee within wrapper %s", wrapper)
+				}
+				if callee.String() != entry.callee {
+					t.Errorf("Expected callee in wrapper %q is %q. got %q", v, entry.callee, callee)
+				}
+			})
+		}
 	}
 }
 
@@ -707,6 +711,9 @@ func TestTypeparamTest(t *testing.T) {
 	}
 
 	for _, entry := range list {
+		if entry.Name() == "issue376214.go" {
+			continue // investigate variadic + New signature.
+		}
 		if entry.IsDir() || !strings.HasSuffix(entry.Name(), ".go") {
 			continue // Consider standalone go files.
 		}
@@ -746,7 +753,8 @@ func TestTypeparamTest(t *testing.T) {
 				t.Fatalf("conf.Load(%s) failed: %s", input, err)
 			}
 
-			prog := ssautil.CreateProgram(iprog, ssa.SanityCheckFunctions)
+			mode := ssa.SanityCheckFunctions | ssa.InstantiateGenerics
+			prog := ssautil.CreateProgram(iprog, mode)
 			prog.Build()
 		})
 	}
@@ -784,7 +792,7 @@ func sliceMax(s []int) []int { return s[a():b():c()] }
 	}
 
 	// Create and build SSA
-	prog := ssautil.CreateProgram(lprog, 0)
+	prog := ssautil.CreateProgram(lprog, ssa.BuilderMode(0))
 	p := prog.Package(lprog.Package("p").Pkg)
 	p.Build()