proposal: cmd/compile: intrinsicify user defined assembly functions

[minux]

I'd like the compiler to intrinsicify user defined assembly functions.

here is a simple sketch of the user interface:
we introduce CLOBBER pseudo instruction to describe that after
certain instruction, certain registers are clobbered.

When the user defines such an assembly function in a package:
TEXT ·Clz(SB), NOSPLIT, $0-4
MOVW 0(FP), R0 // compiler recognizes this as input read
CLZ R0, R1 // the new instruction template
CLOBBER [R2-R3, R11] // as an example of CLOBBER, so that compiler know to spill those registers before using this instruction template
MOVW R1, 4(FP) // compiler recognizes this as output write
RET

The user effectively tells the compiler a new rule to expand call
to Clz function with a custom instruction CLZ.

If we ignore the possibility of doing register allocation for the new
instruction template, I think instrinsicify such assembly functions
with the current SSA backend is within reach.

Of course, this has implications on safety, but if the user is already
using assembly, then that shouldn't be a big concern.

[rsc]

I think this would be a significant source of complexity for very little benefit. I do think we need a story for access to functionality like this, but a decent package API for bit twiddling, known to the compiler the same way math.Sqrt is known, should suffice.

Also note that today the Go compiler runs before the assembler, because it generates go_asm.h for use by assembly code. In addition to the complexity of somehow interpreting these magic "inline assembly in another file" stanzas, we'd have to run the compiler, run the assembler, and run the compiler again.

/cc @dr2chase

[minux]

The SIMD instructions don't map well to Go's strict typing. For example, suppose we have SIMD types for [4]float32, [8]uint16, but some functions like bitwise operations could apply to both, either we define separate intrinsic functions that take different types, or we somehow make the function "generic" using compiler magic. Neither solution is ideal. Or we can define a generic 128-bit SIMD type that is accepted by all SIMD intrinsics, but provide conversion functions that extract different kinds (float32, float64, uint8, uint16) of component from the generic 128-bit type. This will reduce the number of SIMD intrinsics functions but then it's like programming with interface{} only.

[randall77]

In Go 1.8 we intrinsify some operations in runtime/internal/sys which includes CLZ mentioned in this issue.

The intrinsification is easy to extend to a user-exposed package (we already do so for sync/atomic). The hard part is coming up with APIs to access these ops. The instructions across architectures can vary on what they do in corner cases (e.g. CLZ with a zero argument). Do you expose that in the API, or introduce fixup code to make the API clean but slower? We can afford to be sloppy in runtime/internal but for something external and under the Go1 guarantee it is harder.

Doesn't help with generic assembly inlining, but it may help a bunch of the common cases.

[minux]

Yeah, designing an API to access the special instructions is the hard part. I think the essence of the issue is to provide some kind of user defined SSA rewrite rules (that can expand to instructions unknown to cmd/internal/obj). We can be creative, the end user interface doesn't have to be an assembly file (in fact, using the assembly file as input means the compiler must somehow infer the allowed register, or forced to use the one used by the assembly function.)

[josharian]

The hard part is coming up with APIs to access these ops. The instructions across architectures can vary on what they do in corner cases (e.g. CLZ with a zero argument). Do you expose that in the API, or introduce fixup code to make the API clean but slower?

I would really love a fast bit-twiddling package in std. I'd suggest introducing fixup code to make the API clean but slower. I suspect most of these cleanups would be a single highly predictable branch anyway. For many bit-twiddling operations we already have two existing users, the runtime and math/big. That should help some with API design.

The SIMD instructions don't map well to Go's strict typing.

One option is to have package-specific SIMD types, which correspond to SIMD register widths. Then all functions in the package operate on those types, e.g. AddUint32x4(dst, src1, src2 Reg128). We'd provide a bunch of Load/Store functions, e.g. LoadUint64x2(p *[2]uint64) Reg128 and StoreUint64x2(p *[2]uint64, r Reg128). Maybe also pointer-free variants. This corresponds reasonably well to what happens under the hood--data gets loaded into a register, manipulated into that register, and then stored back into memory--which is probably a good thing for such low-level operations. It looks a fair amount like the C intrinsics (be that good or bad). And it'd make the job of the register allocator way easier.

We can be creative, the end user interface doesn't have to be an assembly
file

Interesting. Something a la cgo? But then we have a third DSL to parse, maintain, etc. Seems like we should start with bit-twiddling and maybe SIMD.

[rsc]

I think the essence of the issue is to provide some kind of user defined SSA rewrite rules (that can expand to instructions unknown to cmd/internal/obj).

I think this would be a serious mistake. It exposes compiler internals that are internals. We do not want them to become the public API of the toolchain. The other problem with designing a general low-level mechanism is that then you're asking everyone to be low-level users.

Instead, find the higher-level things that are not easily accessed (vector math, bit twiddling) and write a good API for them. Yes, good API design is hard. All the more reason to do it once.

[brtzsnr]

Related to bit-twiddling I made a survey of the available libraries before #10757. On the bug Rob opposed including bit-twidling library as a standard library. Is supporting an external library (e.g. golang.org/bittwiddling) by the compiler fine?

If one were to work on a proposal for a bit-twiddling, what would the timeline be for inclusion in Go1.9?

[randall77]

I don't think it makes sense for the compiler to reference anything outside the stdlib. When semantic inlining, you really want the code you are semantic inlining and the compiler to be released in lock step.

A proposal for a bit-twiddling library would be good. Probably want that out by Feb 1 so we can discuss + implement in time for 1.9.
Check out runtime/internal/sys/intrinsics.go, we'd want at least these.

[minux]

On Thu, Jan 5, 2017 at 9:40 AM, Russ Cox ***@***.***> wrote: I think the essence of the issue is to provide some kind of user defined SSA rewrite rules (that can expand to instructions unknown to cmd/internal/obj). I think this would be a serious mistake. It exposes compiler internals that are *internals*. We do not want them to become the public API of the toolchain. The other problem with designing a general low-level mechanism is that then you're asking everyone to be low-level users. Instead, find the higher-level things that are not easily accessed (vector math, bit twiddling) and write a good API for them. Yes, good API design is hard. All the more reason to do it once.

I'm not proposing to expose the current SSA rule to the user. I'm proposing to design and expose a suitable way to make arbitrary instruction sequence available to Go programs as an inlinable function, and in fact, I think most, if not all, use cases just require one instruction to be available to Go. gcc's extended inline assembly is one such interface, but I think we can do better (no, I'm not proposing inline assembly for Go. The instruction templates should be in a separate file.) Designing a high-level API, by definition, won't remove all the needs for custom assembly functions, because the API can't be future-proof and processor vendors will keep adding more and more specialized instructions. And one more reason why we should do it at the tool level, not as a std package: the Go 1 compatibility makes designing good abstraction pretty hard, and because the nature of this problem, we can't design the API in a package in a subrepo (e.g. x/simd) like context or http2 and later move it into std when it's mature. Instead, we can start with the tool level support and see what the community come up with. When we have a really nice API come up, we can then absorb it as a standard package. Exposing the low-level mechanism makes experiments with the API possible. Of course, there is an alternative way to do the API experiments. We can have a package in a sub-repo, with functions backed by assembly functions. But I'd argue this approach won't work because the function call overhead is prohibitive for small intrinsics and if the package doesn't bring significant speedups, users simply won't use it. And without many users, how can we evaluate the API decisions?

[rsc]

I'd really like to focus our development efforts on whatever the high-level needs are (bit twiddling, etc) and not on the low-level out-of-line inline assembly mechanism.

[rsc]

To be clear, we can easily imagine a beautiful system along these lines that "just works" and makes things transparently run faster with no effort by users. But that's a huge effort that must be implemented, debugged, and maintained (by the core team). We don't believe that this effort is a high enough priority right now compared to other efforts.

-rsc for @golang/proposal-review