Stream: git-wasmtime

Topic: wasmtime / PR #5784 Add `{u,s}{add,sub,mul}_overflow` ins...

view this post on Zulip Wasmtime GitHub notifications bot (Feb 15 2023 at 03:41):

T0b1-iOS opened PR #5784 from arith_of to main:

Currently, there is not really a way to efficiently detect arithmetic over/underflow which some ISAs (in particular x64) allow and can be important. For example, I'm currently trialing Cranelift as a backend in a database system which needs efficient overflow handling.
There also seems to be more general interest in overflow detection (see #1044).

This PR adds instructions for unsigned and signed add/sub/mul which return a second output indicating overflow.
add/sub support 8 through 128 bit integers while the mul variants only support up to 64 bit integers. (That's because the most efficient implementation for umul_overflow with 128bit integers is along the lines of 50 instructions on x64 at which point it is probably better to emit a function call).
I left iadd_cout and friends untouched as the semantics are a bit confusing right now, e.g. iadd_cout seems to be indicating signed overflow while the pseudocode in the description describes unsigned overflow).

In detail, this PR adds:

Currently, there are no emit tests since they were not important for the initial testing and I would like to know whether there is interest in these instructions being included first.
Additionally, the 128bit lowerings currently forego the flag helpers since they are, as far as I can tell, not really designed to produce three outputs so getting both the low/high part of an addition and the dst reg for a setcc seemed a bit complicated.
I also do not have a lot of knowledge about RV64/S390X so I don't think I can provide lowerings there.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 03:12):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 03:27):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 20:36):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 21:05):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 21:07):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 21:12):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 25 2023 at 22:32):

T0b1-iOS has marked PR #5784 as ready for review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 26 2023 at 23:47):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 11:58):

afonso360 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 11:58):

afonso360 created PR review comment:

This description does not seem correct, since we use ints(Interval::All) below, which does include I128's.

The descriptions for umul_overflow/smul_overflow also state something similar.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 11:58):

afonso360 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

s/a arithmetic/an arithmetic/

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

small style nit, but I prefer a more functional style here, where instead of a mut binding, we do let (op, size) = match alu_op { ... } and produce original size or an overridden one in each match arm.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

It's somewhat surprising here that we take an arbitrary Cond, given that the helper name is specifically "overflow"-related; could we document which Conds we expect, or if it's only one in practice, just name it directly?

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

I usually prefer to avoid bool flags unless the meaning is really clear from the name. Here it's not clear from the name whether true means zero or sign-extend. (And we've had one CVE from confusing these so the difference is important!) Could we define a purpose-built enum with Zero and Sign arms, if we don't have one elsewhere that we can use, and use it here and in callers as appropriate?

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

We usually use the terminology "narrow" to describe types narrower than the native operator/instruction width. Not a huge deal but probably nice for future readability.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

Let's extend the helper so we can -- it's the way we use to avoid subtle bugs from out-of-order emits and unexpected side-effects.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

Is there any reason we can't use the ordinary mul in the AluRmiR? Alternately, if we do this, we should remove it completely from AluRmiROpcode and switch uses over -- there shouldn't be two different ways to build a MachInst for it.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

Here as well, let's extend with_flags rather than doing an ad-hoc emit.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 19:28):

cfallin created PR review comment:

It might make the tests a little easier to read and maintain if we use multiple-returns here -- if we return -> i128, i8 and compare against [val, of] we can collapse this with the below. See e.g. runtests/i128-concat-split.clif for an example.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 20:45):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 20:45):

T0b1-iOS created PR review comment:

AluRmiROpcode.Mul is a signed multiply, it emits imul. This one emits mul, which is unsigned multiplication. I added it as a new MachInst since the implementation for the AluRmiR mul operation states that it is freeloaded into the MachInst and doesn't really fit it already so I didn't add a AluRmiROpcode.UMul.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 20:56):

cfallin created PR review comment:

Ah! I had missed that difference; thanks. This is indeed fine then.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 20:56):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 21:56):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 21:56):

T0b1-iOS created PR review comment:

The problem is that currently with_flags returns a ValueRegs which can hold at max 2 values but the 128bit implementations for the overflow ops would need three return values.
So I could change the with_flags helper to return an InstOutput maybe and change all the places it's used to accomodate this but that would probably be quite a big change.
Or should I simply implement a new helper (e.g. with_flags_extended) that can return an InstOutput?
And should I use InstOutput or create a new type to handle more than one ValueRegs. Though I think the notion of InstOuput with multiple ValueRegs is already quite fitting.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:07):

T0b1-iOS updated PR #5784 from arith_of to main.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:08):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:08):

T0b1-iOS created PR review comment:

Thanks for catching that, it should be correct now. I also added your changes for the fuzzer.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:08):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:08):

T0b1-iOS created PR review comment:

I added a description which conditions are used.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:09):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:09):

T0b1-iOS created PR review comment:

I changed that.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:09):

T0b1-iOS edited PR review comment.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:11):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:11):

T0b1-iOS created PR review comment:

I changed it to use the ArgumentExtension enum which I thought is fitting enough. I also changed the lower_extend_op helper to use ArgumentExtension since that was using a bool before also.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:13):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 27 2023 at 22:13):

T0b1-iOS created PR review comment:

I changed the description. Is it better now?

view this post on Zulip Wasmtime GitHub notifications bot (Mar 29 2023 at 00:24):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 29 2023 at 00:24):

cfallin created PR review comment:

Hmm -- yeah, with_flags_extended seems like a better option here.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 29 2023 at 00:25):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 29 2023 at 00:25):

cfallin created PR review comment:

Yep, thanks!

view this post on Zulip Wasmtime GitHub notifications bot (Mar 29 2023 at 00:25):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 29 2023 at 00:25):

cfallin created PR review comment:

Much better, thank you!

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 20:06):

T0b1-iOS requested elliottt for a review on PR #5784.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 20:06):

T0b1-iOS requested wasmtime-compiler-reviewers for a review on PR #5784.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 20:06):

T0b1-iOS updated PR #5784.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 20:08):

T0b1-iOS created PR review comment:

I added the helper now. I added a new ProducesFlags variant that combines two ProducesFlagsReturnsResultWithConsumer. I also added a few helper to extract the values out of the InstOutput afterwards which involves a bit of trickery to extract ValueRegs from it using a reference. You might want to look at that (all that mentions InstOutputRef).
I also renamed produces_flags_append to produces_flags_concat to be in-line with consumes_flags_concat.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 20:08):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 21:06):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 21:06):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 21:06):

cfallin created PR review comment:

Hmm, now that I see this with InstOutputRef, I don't think this is very readable either; making the "extended" variant of the combinator take only the specific combination we need feels odd too. The second ProducesFlags also consumes flags from the previous op, which makes it a bit of an impedance mismatch too.

I think something like this would (finally!) work though:

(type MultiReg (Three (a Reg) (b Reg) (c Reg))

(decl with_flags_chain (ProducesFlags ProducesAndConsumesFlags ConsumesFlags) MultiReg)

;; inst constructor that turns `adcs` (aarch64) or `add` (x64) into a `ProducesAndConsumesFlags`

;; then:

(decl pair_and_single (MultiReg) InstOutput)
(rule (pair_and_single (MultiReg.Three a b c)
  (output_pair (value_regs a b) c))

does that seem reasonable?

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 21:50):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 21:50):

T0b1-iOS created PR review comment:

The second ProducesFlags also consumes flags from the previous op, which makes it a bit of an impedance mismatch too.
That is true, though the ccmp constructor on arm does the same thing with ProducesFlagsTwiceSideEffect.

The rest is reasonable, i guess, though I'd need to implement more generic inst constructors for alu_rmi_r/alu_rrr that construct a ConsumesAndProducesFlags (probably better ordered like that) since the helpers do not know which alu op they are constructing specifically.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 03 2023 at 21:50):

T0b1-iOS edited PR review comment.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2023 at 23:33):

T0b1-iOS updated PR #5784.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2023 at 23:35):

T0b1-iOS submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2023 at 23:35):

T0b1-iOS created PR review comment:

I replaced the old change with what you proposed. It supports more combinations now, though that ended up in a lot of copypaste.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 11 2023 at 18:37):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 11 2023 at 19:44):

T0b1-iOS updated PR #5784.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 11 2023 at 20:15):

cfallin has enabled auto merge for PR #5784.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 11 2023 at 20:53):

cfallin merged PR #5784.

Last updated: Dec 23 2024 at 12:05 UTC