[dev.typeparams] cmd/compile: simplify SSA devirtualization

This CL implements a few improvements to SSA devirtualization to make
it simpler and more general:

1. Change reflectdata.ITabAddr to now immediately generate the wrapper
functions and write out the itab symbol data. Previously, these were
each handled by separate phases later on.

2. Removes the hack in typecheck where we marked itabs that we
expected to need later. Instead, the calls to ITabAddr in walk now
handle generating the wrappers.

3. Changes the SSA interface call devirtualization algorithm to just
use the itab symbol data (namely, its relocations) to figure out what
pointer is available in memory at the given offset. This decouples it
somewhat from reflectdata.

Change-Id: I8fe06922af8f8a1e7c93f5aff2b60ff59b8e7114
Reviewed-on: https://go-review.googlesource.com/c/go/+/327871
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>

9 files changed, 92 insertions, 189 deletions

diff --git a/src/cmd/compile/internal/escape/escape.go b/src/cmd/compile/internal/escape/escape.go
index 842b0f4a7e..e3727bca27 100644
--- a/src/cmd/compile/internal/escape/escape.go
+++ b/src/cmd/compile/internal/escape/escape.go
@@ -673,7 +673,7 @@ func (e *escape) exprSkipInit(k hole, n ir.Node) {
 		n := n.(*ir.BinaryExpr)
 		// Note: n.X is not needed because it can never point to memory that might escape.
 		e.expr(k, n.Y)
-	case ir.OIDATA:
+	case ir.OIDATA, ir.OSPTR:
 		n := n.(*ir.UnaryExpr)
 		e.expr(k, n.X)
 	case ir.OSLICE2ARRPTR:
diff --git a/src/cmd/compile/internal/gc/main.go b/src/cmd/compile/internal/gc/main.go
index ce50cbb4c2..c0346c0206 100644
--- a/src/cmd/compile/internal/gc/main.go
+++ b/src/cmd/compile/internal/gc/main.go
@@ -181,7 +181,6 @@ func Main(archInit func(*ssagen.ArchInfo)) {
 
 	typecheck.Target = new(ir.Package)
 
-	typecheck.NeedITab = func(t, iface *types.Type) { reflectdata.ITabAddr(t, iface) }
 	typecheck.NeedRuntimeType = reflectdata.NeedRuntimeType // TODO(rsc): TypeSym for lock?
 
 	base.AutogeneratedPos = makePos(src.NewFileBase("<autogenerated>", "<autogenerated>"), 1, 0)
@@ -193,6 +192,11 @@ func Main(archInit func(*ssagen.ArchInfo)) {
 
 	dwarfgen.RecordPackageName()
 
+	// Prepare for backend processing. This must happen before pkginit,
+	// because it generates itabs for initializing global variables.
+	typecheck.InitRuntime()
+	ssagen.InitConfig()
+
 	// Build init task.
 	if initTask := pkginit.Task(); initTask != nil {
 		typecheck.Export(initTask)
@@ -252,6 +256,11 @@ func Main(archInit func(*ssagen.ArchInfo)) {
 	base.Timer.Start("fe", "escapes")
 	escape.Funcs(typecheck.Target.Decls)
 
+	// TODO(mdempsky): This is a hack. We need a proper, global work
+	// queue for scheduling function compilation so components don't
+	// need to adjust their behavior depending on when they're called.
+	reflectdata.AfterGlobalEscapeAnalysis = true
+
 	// Collect information for go:nowritebarrierrec
 	// checking. This must happen before transforming closures during Walk
 	// We'll do the final check after write barriers are
@@ -260,17 +269,7 @@ func Main(archInit func(*ssagen.ArchInfo)) {
 		ssagen.EnableNoWriteBarrierRecCheck()
 	}
 
-	// Prepare for SSA compilation.
-	// This must be before CompileITabs, because CompileITabs
-	// can trigger function compilation.
-	typecheck.InitRuntime()
-	ssagen.InitConfig()
-
-	// Just before compilation, compile itabs found on
-	// the right side of OCONVIFACE so that methods
-	// can be de-virtualized during compilation.
 	ir.CurFunc = nil
-	reflectdata.CompileITabs()
 
 	// Compile top level functions.
 	// Don't use range--walk can add functions to Target.Decls.
diff --git a/src/cmd/compile/internal/gc/obj.go b/src/cmd/compile/internal/gc/obj.go
index 8a2ff75583..440f898211 100644
--- a/src/cmd/compile/internal/gc/obj.go
+++ b/src/cmd/compile/internal/gc/obj.go
@@ -117,7 +117,7 @@ func dumpdata() {
 	addsignats(typecheck.Target.Externs)
 	reflectdata.WriteRuntimeTypes()
 	reflectdata.WriteTabs()
-	numPTabs, numITabs := reflectdata.CountTabs()
+	numPTabs := reflectdata.CountPTabs()
 	reflectdata.WriteImportStrings()
 	reflectdata.WriteBasicTypes()
 	dumpembeds()
@@ -158,13 +158,10 @@ func dumpdata() {
 	if numExports != len(typecheck.Target.Exports) {
 		base.Fatalf("Target.Exports changed after compile functions loop")
 	}
-	newNumPTabs, newNumITabs := reflectdata.CountTabs()
+	newNumPTabs := reflectdata.CountPTabs()
 	if newNumPTabs != numPTabs {
 		base.Fatalf("ptabs changed after compile functions loop")
 	}
-	if newNumITabs != numITabs {
-		base.Fatalf("itabs changed after compile functions loop")
-	}
 }
 
 func dumpLinkerObj(bout *bio.Writer) {
diff --git a/src/cmd/compile/internal/reflectdata/reflect.go b/src/cmd/compile/internal/reflectdata/reflect.go
index f4a0619935..9e070895a0 100644
--- a/src/cmd/compile/internal/reflectdata/reflect.go
+++ b/src/cmd/compile/internal/reflectdata/reflect.go
@@ -28,23 +28,13 @@ import (
 	"cmd/internal/src"
 )
 
-type itabEntry struct {
-	t, itype *types.Type
-	lsym     *obj.LSym // symbol of the itab itself
-
-	// symbols of each method in
-	// the itab, sorted by byte offset;
-	// filled in by CompileITabs
-	entries []*obj.LSym
-}
-
 type ptabEntry struct {
 	s *types.Sym
 	t *types.Type
 }
 
-func CountTabs() (numPTabs, numITabs int) {
-	return len(ptabs), len(itabs)
+func CountPTabs() int {
+	return len(ptabs)
 }
 
 // runtime interface and reflection data structures
@@ -56,7 +46,6 @@ var (
 	gcsymmu  sync.Mutex // protects gcsymset and gcsymslice
 	gcsymset = make(map[*types.Type]struct{})
 
-	itabs []itabEntry
 	ptabs []*ir.Name
 )
 
@@ -841,16 +830,16 @@ func TypePtr(t *types.Type) *ir.AddrExpr {
 	return typecheck.Expr(typecheck.NodAddr(n)).(*ir.AddrExpr)
 }
 
-func ITabAddr(t, itype *types.Type) *ir.AddrExpr {
-	if t == nil || (t.IsPtr() && t.Elem() == nil) || t.IsUntyped() || !itype.IsInterface() || itype.IsEmptyInterface() {
-		base.Fatalf("ITabAddr(%v, %v)", t, itype)
-	}
-	s, existed := ir.Pkgs.Itab.LookupOK(t.ShortString() + "," + itype.ShortString())
+// ITabAddr returns an expression representing a pointer to the itab
+// for concrete type typ implementing interface iface.
+func ITabAddr(typ, iface *types.Type) *ir.AddrExpr {
+	s, existed := ir.Pkgs.Itab.LookupOK(typ.ShortString() + "," + iface.ShortString())
+	lsym := s.Linksym()
+
 	if !existed {
-		itabs = append(itabs, itabEntry{t: t, itype: itype, lsym: s.Linksym()})
+		writeITab(lsym, typ, iface)
 	}
 
-	lsym := s.Linksym()
 	n := ir.NewLinksymExpr(base.Pos, lsym, types.Types[types.TUINT8])
 	return typecheck.Expr(typecheck.NodAddr(n)).(*ir.AddrExpr)
 }
@@ -1223,83 +1212,6 @@ func InterfaceMethodOffset(ityp *types.Type, i int64) int64 {
 	return int64(commonSize()+4*types.PtrSize+uncommonSize(ityp)) + i*8
 }
 
-// for each itabEntry, gather the methods on
-// the concrete type that implement the interface
-func CompileITabs() {
-	for i := range itabs {
-		tab := &itabs[i]
-		methods := genfun(tab.t, tab.itype)
-		if len(methods) == 0 {
-			continue
-		}
-		tab.entries = methods
-	}
-}
-
-// for the given concrete type and interface
-// type, return the (sorted) set of methods
-// on the concrete type that implement the interface
-func genfun(t, it *types.Type) []*obj.LSym {
-	if t == nil || it == nil {
-		return nil
-	}
-	sigs := imethods(it)
-	methods := methods(t)
-	out := make([]*obj.LSym, 0, len(sigs))
-	// TODO(mdempsky): Short circuit before calling methods(t)?
-	// See discussion on CL 105039.
-	if len(sigs) == 0 {
-		return nil
-	}
-
-	// both sigs and methods are sorted by name,
-	// so we can find the intersect in a single pass
-	for _, m := range methods {
-		if m.name == sigs[0].name {
-			out = append(out, m.isym)
-			sigs = sigs[1:]
-			if len(sigs) == 0 {
-				break
-			}
-		}
-	}
-
-	if len(sigs) != 0 {
-		base.Fatalf("incomplete itab")
-	}
-
-	return out
-}
-
-// ITabSym uses the information gathered in
-// CompileITabs to de-virtualize interface methods.
-// Since this is called by the SSA backend, it shouldn't
-// generate additional Nodes, Syms, etc.
-func ITabSym(it *obj.LSym, offset int64) *obj.LSym {
-	var syms []*obj.LSym
-	if it == nil {
-		return nil
-	}
-
-	for i := range itabs {
-		e := &itabs[i]
-		if e.lsym == it {
-			syms = e.entries
-			break
-		}
-	}
-	if syms == nil {
-		return nil
-	}
-
-	// keep this arithmetic in sync with *itab layout
-	methodnum := int((offset - 2*int64(types.PtrSize) - 8) / int64(types.PtrSize))
-	if methodnum >= len(syms) {
-		return nil
-	}
-	return syms[methodnum]
-}
-
 // NeedRuntimeType ensures that a runtime type descriptor is emitted for t.
 func NeedRuntimeType(t *types.Type) {
 	if t.HasTParam() {
@@ -1346,29 +1258,57 @@ func WriteRuntimeTypes() {
 	}
 }
 
-func WriteTabs() {
-	// process itabs
-	for _, i := range itabs {
-		// dump empty itab symbol into i.sym
-		// type itab struct {
-		//   inter  *interfacetype
-		//   _type  *_type
-		//   hash   uint32
-		//   _      [4]byte
-		//   fun    [1]uintptr // variable sized
-		// }
-		o := objw.SymPtr(i.lsym, 0, writeType(i.itype), 0)
-		o = objw.SymPtr(i.lsym, o, writeType(i.t), 0)
-		o = objw.Uint32(i.lsym, o, types.TypeHash(i.t)) // copy of type hash
-		o += 4                                          // skip unused field
-		for _, fn := range genfun(i.t, i.itype) {
-			o = objw.SymPtrWeak(i.lsym, o, fn, 0) // method pointer for each method
-		}
-		// Nothing writes static itabs, so they are read only.
-		objw.Global(i.lsym, int32(o), int16(obj.DUPOK|obj.RODATA))
-		i.lsym.Set(obj.AttrContentAddressable, true)
+// writeITab writes the itab for concrete type typ implementing
+// interface iface.
+func writeITab(lsym *obj.LSym, typ, iface *types.Type) {
+	// TODO(mdempsky): Fix methodWrapper, geneq, and genhash (and maybe
+	// others) to stop clobbering these.
+	oldpos, oldfn := base.Pos, ir.CurFunc
+	defer func() { base.Pos, ir.CurFunc = oldpos, oldfn }()
+
+	if typ == nil || (typ.IsPtr() && typ.Elem() == nil) || typ.IsUntyped() || iface == nil || !iface.IsInterface() || iface.IsEmptyInterface() {
+		base.Fatalf("writeITab(%v, %v)", typ, iface)
+	}
+
+	sigs := iface.AllMethods().Slice()
+	entries := make([]*obj.LSym, 0, len(sigs))
+
+	// both sigs and methods are sorted by name,
+	// so we can find the intersection in a single pass
+	for _, m := range methods(typ) {
+		if m.name == sigs[0].Sym {
+			entries = append(entries, m.isym)
+			sigs = sigs[1:]
+			if len(sigs) == 0 {
+				break
+			}
+		}
+	}
+	if len(sigs) != 0 {
+		base.Fatalf("incomplete itab")
+	}
+
+	// dump empty itab symbol into i.sym
+	// type itab struct {
+	//   inter  *interfacetype
+	//   _type  *_type
+	//   hash   uint32
+	//   _      [4]byte
+	//   fun    [1]uintptr // variable sized
+	// }
+	o := objw.SymPtr(lsym, 0, writeType(iface), 0)
+	o = objw.SymPtr(lsym, o, writeType(typ), 0)
+	o = objw.Uint32(lsym, o, types.TypeHash(typ)) // copy of type hash
+	o += 4                                        // skip unused field
+	for _, fn := range entries {
+		o = objw.SymPtrWeak(lsym, o, fn, 0) // method pointer for each method
 	}
+	// Nothing writes static itabs, so they are read only.
+	objw.Global(lsym, int32(o), int16(obj.DUPOK|obj.RODATA))
+	lsym.Set(obj.AttrContentAddressable, true)
+}
 
+func WriteTabs() {
 	// process ptabs
 	if types.LocalPkg.Name == "main" && len(ptabs) > 0 {
 		ot := 0
@@ -1926,20 +1866,10 @@ func methodWrapper(rcvr *types.Type, method *types.Field, forItab bool) *obj.LSy
 	ir.CurFunc = fn
 	typecheck.Stmts(fn.Body)
 
-	// TODO(mdempsky): Make this unconditional. The exporter now
-	// includes all of the inline bodies we need, and the "importedType"
-	// logic above now correctly suppresses compiling out-of-package
-	// types that we might not have inline bodies for. The only problem
-	// now is that the extra inlining can now introduce further new
-	// itabs, and gc.dumpdata's ad hoc compile loop doesn't handle this.
-	//
-	// CL 327871 will address this by writing itabs and generating
-	// wrappers as part of the loop, so we won't have to worry about
-	// "itabs changed after compile functions loop" errors anymore.
-	if rcvr.IsPtr() && rcvr.Elem() == method.Type.Recv().Type && rcvr.Elem().Sym() != nil {
+	if AfterGlobalEscapeAnalysis {
 		inline.InlineCalls(fn)
+		escape.Batch([]*ir.Func{fn}, false)
 	}
-	escape.Batch([]*ir.Func{fn}, false)
 
 	ir.CurFunc = nil
 	typecheck.Target.Decls = append(typecheck.Target.Decls, fn)
@@ -1947,6 +1877,12 @@ func methodWrapper(rcvr *types.Type, method *types.Field, forItab bool) *obj.LSy
 	return lsym
 }
 
+// AfterGlobalEscapeAnalysis tracks whether package gc has already
+// performed the main, global escape analysis pass. If so,
+// methodWrapper takes responsibility for escape analyzing any
+// generated wrappers.
+var AfterGlobalEscapeAnalysis bool
+
 var ZeroSize int64
 
 // MarkTypeUsedInInterface marks that type t is converted to an interface.
diff --git a/src/cmd/compile/internal/ssa/config.go b/src/cmd/compile/internal/ssa/config.go
index 61c65f9e54..b08a394368 100644
--- a/src/cmd/compile/internal/ssa/config.go
+++ b/src/cmd/compile/internal/ssa/config.go
@@ -149,12 +149,6 @@ type Frontend interface {
 	// for the parts of that compound type.
 	SplitSlot(parent *LocalSlot, suffix string, offset int64, t *types.Type) LocalSlot
 
-	// DerefItab dereferences an itab function
-	// entry, given the symbol of the itab and
-	// the byte offset of the function pointer.
-	// It may return nil.
-	DerefItab(sym *obj.LSym, offset int64) *obj.LSym
-
 	// Line returns a string describing the given position.
 	Line(src.XPos) string
 
diff --git a/src/cmd/compile/internal/ssa/rewrite.go b/src/cmd/compile/internal/ssa/rewrite.go
index 375c4d5a56..115d563933 100644
--- a/src/cmd/compile/internal/ssa/rewrite.go
+++ b/src/cmd/compile/internal/ssa/rewrite.go
@@ -745,27 +745,21 @@ func uaddOvf(a, b int64) bool {
 	return uint64(a)+uint64(b) < uint64(a)
 }
 
-// de-virtualize an InterCall
-// 'sym' is the symbol for the itab
-func devirt(v *Value, aux Aux, sym Sym, offset int64) *AuxCall {
-	f := v.Block.Func
-	n, ok := sym.(*obj.LSym)
-	if !ok {
+// loadLSymOffset simulates reading a word at an offset into a
+// read-only symbol's runtime memory. If it would read a pointer to
+// another symbol, that symbol is returned. Otherwise, it returns nil.
+func loadLSymOffset(lsym *obj.LSym, offset int64) *obj.LSym {
+	if lsym.Type != objabi.SRODATA {
 		return nil
 	}
-	lsym := f.fe.DerefItab(n, offset)
-	if f.pass.debug > 0 {
-		if lsym != nil {
-			f.Warnl(v.Pos, "de-virtualizing call")
-		} else {
-			f.Warnl(v.Pos, "couldn't de-virtualize call")
+
+	for _, r := range lsym.R {
+		if int64(r.Off) == offset && r.Type&^objabi.R_WEAK == objabi.R_ADDR && r.Add == 0 {
+			return r.Sym
 		}
 	}
-	if lsym == nil {
-		return nil
-	}
-	va := aux.(*AuxCall)
-	return StaticAuxCall(lsym, va.abiInfo)
+
+	return nil
 }
 
 // de-virtualize an InterLECall
@@ -776,18 +770,14 @@ func devirtLESym(v *Value, aux Aux, sym Sym, offset int64) *obj.LSym {
 		return nil
 	}
 
-	f := v.Block.Func
-	lsym := f.fe.DerefItab(n, offset)
-	if f.pass.debug > 0 {
+	lsym := loadLSymOffset(n, offset)
+	if f := v.Block.Func; f.pass.debug > 0 {
 		if lsym != nil {
 			f.Warnl(v.Pos, "de-virtualizing call")
 		} else {
 			f.Warnl(v.Pos, "couldn't de-virtualize call")
 		}
 	}
-	if lsym == nil {
-		return nil
-	}
 	return lsym
 }
 
diff --git a/src/cmd/compile/internal/ssagen/ssa.go b/src/cmd/compile/internal/ssagen/ssa.go
index 0fbb39cfbb..7a6bf878e1 100644
--- a/src/cmd/compile/internal/ssagen/ssa.go
+++ b/src/cmd/compile/internal/ssagen/ssa.go
@@ -7401,10 +7401,6 @@ func (e *ssafn) Auto(pos src.XPos, t *types.Type) *ir.Name {
 	return typecheck.TempAt(pos, e.curfn, t) // Note: adds new auto to e.curfn.Func.Dcl list
 }
 
-func (e *ssafn) DerefItab(it *obj.LSym, offset int64) *obj.LSym {
-	return reflectdata.ITabSym(it, offset)
-}
-
 // SplitSlot returns a slot representing the data of parent starting at offset.
 func (e *ssafn) SplitSlot(parent *ssa.LocalSlot, suffix string, offset int64, t *types.Type) ssa.LocalSlot {
 	node := parent.N
diff --git a/src/cmd/compile/internal/typecheck/subr.go b/src/cmd/compile/internal/typecheck/subr.go
index 0e306eaea8..79b2402fe7 100644
--- a/src/cmd/compile/internal/typecheck/subr.go
+++ b/src/cmd/compile/internal/typecheck/subr.go
@@ -379,14 +379,6 @@ func Assignop(src, dst *types.Type) (ir.Op, string) {
 		var missing, have *types.Field
 		var ptr int
 		if implements(src, dst, &missing, &have, &ptr) {
-			// Call NeedITab/ITabAddr so that (src, dst)
-			// gets added to itabs early, which allows
-			// us to de-virtualize calls through this
-			// type/interface pair later. See CompileITabs in reflect.go
-			if types.IsDirectIface(src) && !dst.IsEmptyInterface() {
-				NeedITab(src, dst)
-			}
-
 			return ir.OCONVIFACE, ""
 		}
 
diff --git a/src/cmd/compile/internal/typecheck/typecheck.go b/src/cmd/compile/internal/typecheck/typecheck.go
index 8454b8d5b3..b1a4e193d6 100644
--- a/src/cmd/compile/internal/typecheck/typecheck.go
+++ b/src/cmd/compile/internal/typecheck/typecheck.go
@@ -24,7 +24,6 @@ var inimport bool // set during import
 var TypecheckAllowed bool
 
 var (
-	NeedITab        = func(t, itype *types.Type) {}
 	NeedRuntimeType = func(*types.Type) {}
 )