x/tools/go/ssa: generate function bodies for parameterized functions

[timothy-king]

This proposal is to update the x/tools/go/ssa package to generate function bodies for parameterized functions. This enables analysis of generic functions and methods from incremental analysis tools (such as those built on x/tools/go/analysis/passes/buildssa) without instantiations from the same package.

This is proposal is a continuation of the discussion in #48525. A full implementation of this proposal is available here https://go-review.googlesource.com/c/tools/+/425496 .

This will make several user visible changes to x/tools:

• For generic functions and methods produced from syntax trees, we build a generic ssa.Function. Type parameters, and types containing them, may now appear as the operands and results of ssa.Instructions. For example, a hypothetical generic min[T] function would contain an instruction corresponding to the binary operation T < T.
• Instances of generic functions may be created in one of two forms, determined by the InstantiateGenerics builder mode flag. (The flag has the same behavior as before this update.)
  • When InstantiateGenerics is disabled (the default), each instantiation is materialized as a thin wrapper that delegates to the generic function. For example, given a hypothetical generic slices.Reverse[T] function, the instance Reverse[int] would be a wrapper that calls Reverse[T], coercing its argument from []int to []T and its result from []T to []int.
  • When InstantiateGenerics is enabled, each fully instantiated instance is expanded and specialized for its particular types. In this mode, Reverse[int] would contain the complete logic of slice reversal specialized to integers. Partial instantiations are still materialized as wrappers. For example, a generic method TreeMap[K,V].Contains may be partially instantiated to a wrapper TreeMap[string, V].Contains while TreeMap[string, int].Contains is fully expanded and specialized.
• The ChangeType instruction can now represent a coercion to or from a parameterized type to an instance of the type.
• Const values can now represent zero values of any type, including structs, arrays, and type parameters.
• go/analysis/passes/buildssa builds with the default build mode. (ssa.InstantiateGenerics is off.)
• ssa.Function has three, backwards compatible, new methods to help navigate generic functions and instantiations:
  • TypeParams, which returns the function’s list of type parameters;
  • TypeArgs, which returns the instantiations of the function’s type parameters;
  • Origin, which returns the generic function, given one of its instantiations.

Comparison to the current state of ssa and buildssa:

This behavior is mostly an expansion of the existing behavior. Existing users of ssa may have incomplete type switches (no handling of types.TypeParam) or other now incorrect assumptions that are now incorrect for parameterized Functions. This will only apply to analysis of code that uses generics. In practice, many existing drivers of x/tools/go/analysis.Analyzers will examine transitive dependencies. As of Go 1.19 standard library packages such as sync/atomics.Pointer[T] contain generics. So applying ssa to parameterized functions is likely to occur in the analysis of non-toy packages.

The current state of incremental analysis from buildssa is that ssa.InstantiateGenerics is on today. Generic ssa.Functions will be present in SrcFuncs, have types.TypeParams in their Signatures, and have empty bodies. Instantiations within the same package will be built with expanded function bodies. Instantiations of a generic function defined in another packages will not have a syntax tree available and will be built with an empty Function body. To analyze the contents of parameterized functions, a body must be made available without requiring [somewhat complete] instantiations from the same package. If this proposal is accepted, a body for parameterized functions will always be available.

Users that want to skip over the bodies of generic functions (potentially temporarily while they add support) can use fn.TypeParams() > 0 && len(fn.TypesArgs()) == 0 to detect when a function has a parameterized body.

[timothy-king]

CC @findleyr

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

Any objections to adopting this proposal?

/cc @adonovan

[adonovan]

Any objections to adopting this proposal?

None at all! We should merge it as soon as we've verified that the new go/ssa builder is free of obvious bugs by running it over Google's internal Go code base.

Thanks Tim and Zvonimir for your sustained efforts on this tricky problem.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[timothy-king]

We should merge it as soon as we've verified that the new go/ssa builder is free of obvious bugs by running it over Google's internal Go code base.

There are no known bugs with go/ssa over Google's internal Go code base with BuilderMode(0).

[timothy-king]

Implemented in https://go-review.googlesource.com/c/tools/+/425496.