Include byteswap and rotates in the MVP

[mbodart]

Of the integer operations listed in FutureFeatures.md, it seems bswap and the rotates belong in the MVP. I imagine they have as much utility and direct hardware support as popcnt, clz and ctz.

They seem trivial to support, and increase the richness of the MVP, so I don't see why we would defer them.

I created PR WebAssembly/spec#149 for support in the spec interpreter.

Of course, AstSemantics and other tools would need updating as well.

What say all?

+1 to bringing low hanging fruit into the MVP.

[jcbeyler]

+1 too :)

[jfbastien]

Hmm, reading @sunfishcode's comments on #121 I'm a bit confused... It sounds like he added bswap based on a comment, but the description says otherwise because it's hard to polyfill. I don't quite recall.

[sunfishcode]

The observation is: we don't need to worry about the polyfill being slow for operators like these, because it'll be no worse than what apps that need this functionality would do instead.

These operators were removed from the MVP due to a general desire to keep the MVP focused. bswap in particular is tricky because 32-bit and 64-bit bwap begs a 16-bit bswap too. It'd probably have to have the extra behavior of zeroing the high 16 bits, and it'd be asymmetric between i32 and i64. And, since some architectures fold bswaps into loads and stores (e.g. x86's movbe instruction, and other architectures have similar things), would it be better to have an optional endian attribute on regular loads and stores, instead of a standalone integer operator?

Rotates on the other hand are simple and have prominent use cases. :-)

[titzer]

Since this operation is pretty common and there are architectures with this
explicit instruction, this seems OK to me, but I'm not sure if it's
pressing enough to add to MVP. We'll probably implement this "just for fun"
but not sure all engines need to in MVP.

On Thu, Oct 22, 2015 at 8:17 PM, Dan Gohman notifications@github.com
wrote:

The observation is: we don't need to worry about the polyfill being slow
for operators like these, because it'll be no worse than what apps that
need this functionality would do instead.

These operators were removed from the MVP due to a general desire to keep
the MVP focused. bswap in particular is tricky because 32-bit and 64-bit
bwap begs a 16-bit bswap too. It'd probably have to have the extra behavior
of zeroing the high 16 bits, and it'd be asymmetric between i32 and i64.
And, since some architectures fold bswaps into loads and stores (e.g. x86's
movbe instruction, and other architectures have similar things), would it
be better to have an optional endian attribute on regular loads and stores,
instead of a standalone integer operator?

Rotates on the other hand are simple and have prominent use cases. :-)

—
Reply to this email directly or view it on GitHub
#422 (comment).

[mbodart]

As with any large project I can understand the desire to avoid feature creep in the MVP,
towards keeping schedules manageable and allowing sufficient time for good design.

But bswap and rotate seem straight forward to define and implement, certainly no more difficult,
nor less pressing I would imagine, than popcnt/clz/ctz. Low hanging fruit, as @JSStats put it.
So I don't see what holding them back buys anyone.

The 16-bit argument seems generically applicable to all integer operations.
Adding 32/64-bit flavors now does not inhibit adding 16-bit flavors later.

Bswap is often used in conjunction with memory accesses, so I can understand
some hesitance to add a non-memory form. But the non-memory form can be easily
folded with an i32.load on architectures that support bswap from memory.

From: titzer [mailto:notifications@github.com]
Sent: Thursday, October 22, 2015 9:17 PM
To: WebAssembly/design
Cc: Bodart, Mitch L
Subject: Re: [design] Include byteswap and rotates in the MVP (#422)

Since this operation is pretty common and there are architectures with this
explicit instruction, this seems OK to me, but I'm not sure if it's
pressing enough to add to MVP. We'll probably implement this "just for fun"
but not sure all engines need to in MVP.

On Thu, Oct 22, 2015 at 8:17 PM, Dan Gohman notifications@github.com
wrote:

The observation is: we don't need to worry about the polyfill being slow
for operators like these, because it'll be no worse than what apps that
need this functionality would do instead.

These operators were removed from the MVP due to a general desire to keep
the MVP focused. bswap in particular is tricky because 32-bit and 64-bit
bwap begs a 16-bit bswap too. It'd probably have to have the extra behavior
of zeroing the high 16 bits, and it'd be asymmetric between i32 and i64.
And, since some architectures fold bswaps into loads and stores (e.g. x86's
movbe instruction, and other architectures have similar things), would it
be better to have an optional endian attribute on regular loads and stores,
instead of a standalone integer operator?

Rotates on the other hand are simple and have prominent use cases. :-)

—
Reply to this email directly or view it on GitHub
#422 (comment).

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/422#issuecomment-150463998.

[taisel]

+1 Byteswap stuff being folded into loads and stores as endianness argument.

I also suppose an engine could be smart enough to convert a load/store pattern with the endianness argument directly to a bswap operation with no store/load, if it can be factored out, or at least the store itself rescheduled separately from the bswap operation.

[mbodart]

It appears bswap was not as "slam dunk" as I envisioned.

I still think some form of bswap is appropriate for the MVP, as the alternative emulation sequence with shifts and masks is quite verbose (i.e., non-compact). But for purposes of moving this issue forward, I'm fine with deferring consideration of bswap, and focusing on the rotates for now.

Any objections to adding the rotates?

As I'll need to update the spec PR (and AstSemantics.md), I'll go ahead and switch to the "t" names, rotl and rotr, that are used in the Futures section.

[taisel]

+1 the suite of rotate operations. The bswap stuff can be pattern matched from the shift operations as well. I thought I even saw that already in turbofan... or was that the rotates? Pretty sure a bunch of these can be pattern matched out. I think that's the main objection against including these, as they can be converted from separate shifts to one operation in a pattern match.

So to rephrase the question, is it worthwhile providing distinct operation codes for these rotates and bswaps, or would it improve code density enough to warrant pushing them to the pattern matching side of things? Pattern matching also has overhead in of itself, so that should be considered.

[mbodart]

I'm closing this issue as the rotates have been added.

Byteswaps can be addressed separately, if desired.