Return value devirutalization

[M. C. Sunny Young de la Sota]

Hihi,

I have prepared a CL[1] that implemented the optimization I suggested
way back in go.dev/issue/74392 (and which I discussed with several
compiler folx last week), consisting of three parts:

[1]: https://github.com/golang/go/pull/80809 (still waiting on Gerrit
import, first time contribution at current job)

1. I've rewritten the devirt concrete types analysis. It now keeps
track of a set of potential concrete types for an interface value
(treating nil as its own special type). On its own this improves
devirtualization somewhat. This includes deducing all of the possible
concrete types for results of interface type, which results in
revealing call devirtualization opportunities.

2. I've added a transformation to the inline/devirt pass that splits
functions with devirtualizable results (i.e., results of interface
type with precisely one possible concrete type in the body, on return)
into f, a "a boxing thunk" and f.dv, the "unboxed variant". f
continues to be used for all situations which take the address of f,
but static calls to f are rewritten to calls to f.dv, which avoids
boxing the return values, which in turn elides a heap spill when
returning a non-pointer-shaped concrete type. This is hidden behing a
-d flag.

3. I've made the type set information from (1) available in export
data, which enables cross-package return value devirtualization.

Taken together, this is essentially a transparent variant of Rust's
"impl Trait" syntax, which dodges the cost of an interface while
keeping the tidy API surface. Go can already enable this if the
library author is clever and does the .dv splitting themselves, *and*
knows to mark the .dv variant noinline. In practice, nobody (to first
order approximation) does this.

Codebases which do not benefit see no movement in my benchmarks. I
looked at benchmarking both cmd/compile and the new TypeScript
compiler, neither of which got any worse. On the other hand, in our
(Buf's) compiler(s), we make significant use of interfaces for
abstracting containers (long story short, vanilla slices are
unsuitable for reasons). I have resisted performing the above
optimization (surprising restraint for Sunny) in our codebase because
it litters callsites and we have tons of these "wants to be impl
Interface" functions. In this case, I observed an ~11% improvement in
our stress-test benchmarks for our compiler, running on M1. This is
primarily due to a ~12% drop in calls to mallocgc.

Finding good benchmarks for this has proven difficult, because most of
our (Go at large) large, compute-heavy codebases (rather shrewdly)
avoid using tons of interfaces because of the allocation footgun. TS
is a good example of this. That said, in some rather artificial
microbenchmarks involving hash and image, both of which love returning
interfaces, demonstrated a 2-3x speedup. I have not bothered to hit
this with a randomized branch layout simply because I do not think
such benchmarks are worth more than a footnote.

That aside, I observed that # of new devirt sites correlates somewhat
with improvement in benchmarks, and can share the following data
(including the internal version of Buf's compiler suite):

- std: 2.3x call devirts, 167 .dv splits, 257 unboxed results
- cmd/compile: 2.5x call devirts, 117 .dv splits, 234 unboxed results
- buf: 15.5x call devirts, 87 .dv splits, 2859 (!) unboxed results
- etcd: 10.2x call devirts, 91 .dv splits, 583 unboxed results
- k8s: 2.9x call devirts, 1374 (!!!) .dv splits, 1984 (!) unboxed results

Many devirtualizations appear to come from Protobuf reflection-heavy
users. The protobuf-go reflection API unfortunately misses out on some
of the tricks the reflect package pulls to devirtualize reflect.Type
methods.

I do not believe the above CL is submittable (personally, I would like
to split it into two or three parts). I would like to land these
changes in tip behind the -d flag and discuss what it would take to
flip that flag to default on, ideally in time for 1.28. Feedback for
how to structure this change or acquire is appreciated.

PS: further optimizations. This does not unbox funcval returns,
because I suspect those are rare outside of iterators, which are
already dealt with via what David tells me is an "icky kludge". Many
interface returns are *T, which still allocates in the body. Such
functions could potentially be rewritten to accept a return slot
pointer from the caller, which escape analysis can treat as any other
addrtaken variable. This could further be used on interface returns
which return nil or a concrete type, particularly error returns. I am
not sure this will be especially profitable, since hot (T, error)
returns typically already just toss out an errors.New global or (a
pointer to) an empty struct...

best,
sunny