cmd/compile: enable PGO-driven call devirtualization

This CL is originally based on CL 484838 from rajbarik@uber.com.

Add a new PGO-based devirtualize pass. This pass conditionally
devirtualizes interface calls for the hottest callee. That is, it
performs a transformation like:

	type Iface interface {
		Foo()
	}

	type Concrete struct{}

	func (Concrete) Foo() {}

	func foo(i Iface) {
		i.Foo()
	}

to:

	func foo(i Iface) {
		if c, ok := i.(Concrete); ok {
			c.Foo()
		} else {
			i.Foo()
		}
	}

The primary benefit of this transformation is enabling inlining of the
direct calls.

Today this change has no impact on the escape behavior, as the fallback
interface always forces an escape. But improving escape analysis to take
advantage of this is an area of potential work.

This CL is the bare minimum of a devirtualization implementation. There
are still numerous limitations:

* Callees not directly referenced in the current package can be missed
  (even if they are in the transitive dependences).
* Callees not in the transitive dependencies of the current package are
  missed.
* Only interface method calls are supported, not other indirect function
  calls.
* Multiple calls to compatible interfaces on the same line cannot be
  distinguished and will use the same callee target.
* Callees that only partially implement an interface (they are embedded
  in another type that completes the interface) cannot be devirtualized.
* Others, mentioned in TODOs.

Fixes #59959

Change-Id: I8bedb516139695ee4069650b099d05957b7ce5ee
Reviewed-on: https://go-review.googlesource.com/c/go/+/492436
Reviewed-by: Cherry Mui <cherryyz@google.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Michael Pratt <mpratt@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>

3 files changed, 110 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt.go b/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt.go
new file mode 100644
index 0000000000..3f22093b34
--- /dev/null
+++ b/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt.go
@@ -0,0 +1,83 @@
+// Copyright 2023 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.
+
+// WARNING: Please avoid updating this file. If this file needs to be updated,
+// then a new devirt.pprof file should be generated:
+//
+//	$ cd $GOROOT/src/cmd/compile/internal/test/testdata/pgo/devirtualize/
+//	$ go mod init example.com/pgo/devirtualize
+//	$ go test -bench=. -cpuprofile ./devirt.pprof
+
+package devirt
+
+type Multiplier interface {
+	Multiply(a, b int) int
+}
+
+type Adder interface {
+	Add(a, b int) int
+}
+
+var sink int
+
+type Mult struct{}
+
+func (Mult) Multiply(a, b int) int {
+	for i := 0; i < 1000; i++ {
+		sink++
+	}
+	return a * b
+}
+
+type NegMult struct{}
+
+func (NegMult) Multiply(a, b int) int {
+	for i := 0; i < 1000; i++ {
+		sink++
+	}
+	return -1 * a * b
+}
+
+type Add struct{}
+
+func (Add) Add(a, b int) int {
+	for i := 0; i < 1000; i++ {
+		sink++
+	}
+	return a + b
+}
+
+type Sub struct{}
+
+func (Sub) Add(a, b int) int {
+	for i := 0; i < 1000; i++ {
+		sink++
+	}
+	return a - b
+}
+
+// Exercise calls mostly a1 and m1.
+//
+//go:noinline
+func Exercise(iter int, a1, a2 Adder, m1, m2 Multiplier) {
+	for i := 0; i < iter; i++ {
+		a := a1
+		m := m1
+		if i%10 == 0 {
+			a = a2
+			m = m2
+		}
+
+		// N.B. Profiles only distinguish calls on a per-line level,
+		// making the two calls ambiguous. However because the
+		// interfaces and implementations are mutually exclusive,
+		// devirtualization can still select the correct callee for
+		// each.
+		//
+		// If they were not mutually exclusive (for example, two Add
+		// calls), then we could not definitively select the correct
+		// callee.
+		sink += m.Multiply(42, a.Add(1, 2))
+	}
+}
diff --git a/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt.pprof b/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt.pprof
new file mode 100644
index 0000000000..b72f7cf4b3
--- /dev/null
+++ b/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt.pprof
diff --git a/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt_test.go b/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt_test.go
new file mode 100644
index 0000000000..03c966f6de
--- /dev/null
+++ b/src/cmd/compile/internal/test/testdata/pgo/devirtualize/devirt_test.go
@@ -0,0 +1,27 @@
+// Copyright 2023 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.
+
+// WARNING: Please avoid updating this file. If this file needs to be updated,
+// then a new devirt.pprof file should be generated:
+//
+//	$ cd $GOROOT/src/cmd/compile/internal/test/testdata/pgo/devirtualize/
+//	$ go mod init example.com/pgo/devirtualize
+//	$ go test -bench=. -cpuprofile ./devirt.pprof
+
+package devirt
+
+import (
+	"testing"
+)
+
+func BenchmarkDevirt(b *testing.B) {
+	var (
+		a1 Add
+		a2 Sub
+		m1 Mult
+		m2 NegMult
+	)
+
+	Exercise(b.N, a1, a2, m1, m2)
+}