wasmtime / issue #3747 Missing support for multiple instr... · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / issue #3747 Missing support for multiple instr...

Wasmtime GitHub notifications bot (Feb 01 2022 at 10:20):

uweigand opened issue #3747:

Support for instructions with multiple outputs in ISLE seems to be missing and/or broken at the moment. In general, CLIF instructions may have any number of outputs, each of which may in turn be implemented as one or more registers (i.e. a ValueRegs structure).

However, with ISLE instruction selection, the lower_common helper routine calls the lower ISLE constructor, which only has a _single_ ValueRegs return value. Now, there is some code in lower_common that seems intended to use the registers provides in that single ValueRegs to implement multiple outputs. But that doesn't appear to be working.

In particular, in the common case where we have two outputs with a single register each, and the ISLE lower constructor attempts to handle this by returning two registers in a single ValueRegs, we run into this loop:
    for output in outputs {
        let dsts = get_output_reg(isle_ctx.lower_ctx, *output);
        let ty = isle_ctx.lower_ctx.output_ty(output.insn, output.output);
        let (_, tys) = <C::I>::rc_for_type(ty).unwrap();
        for ((temp, dst), ty) in temp_regs.by_ref().zip(dsts.regs()).zip(tys) {
            renamer.add_rename(*temp, dst.to_reg(), *ty);
        }
    }
The problem here is that due to the way the Rust zip routine works, the first pass through that loop will already consume both registers in temp_regs (the ValueRegs returned from lower). The second pass through the loop will find temp_regs empty and simply not initialize the second output at all.

This isn't an issue at the moment since the only multi-output instruction currently implemented in ISLE is iadd_ifcout, and here the second output is the carry flag, which is ignored as an output anyway (it's handled differently by explicitly matching the combination of the iadd_ifcout and the carry consumer). But if we want to handle instructions that really use multiple outputs (most notably call instructions), this is a problem.

Now, this specific issue can be fixed by doing the zip the other way around. B.t.w. this then actually breaks iadd_ifcout - the current implementations rely on the second output being dropped! That problem can also be fixed e.g. by special-casing IFLAG type outputs. But even then, we can only handle at most two outputs, because any single ValueRegs contains at most two registers.

How is this supposed to be handled? Should lower be changed to return something like a vector of ValueRegs instead of just a single one? Or should there be a different ISLE constructor for multi-output instructions?

CC @cfallin

Wasmtime GitHub notifications bot (Feb 01 2022 at 18:33):

fitzgen labeled issue #3747:

Support for instructions with multiple outputs in ISLE seems to be missing and/or broken at the moment. In general, CLIF instructions may have any number of outputs, each of which may in turn be implemented as one or more registers (i.e. a ValueRegs structure).

However, with ISLE instruction selection, the lower_common helper routine calls the lower ISLE constructor, which only has a _single_ ValueRegs return value. Now, there is some code in lower_common that seems intended to use the registers provides in that single ValueRegs to implement multiple outputs. But that doesn't appear to be working.

In particular, in the common case where we have two outputs with a single register each, and the ISLE lower constructor attempts to handle this by returning two registers in a single ValueRegs, we run into this loop:
    for output in outputs {
        let dsts = get_output_reg(isle_ctx.lower_ctx, *output);
        let ty = isle_ctx.lower_ctx.output_ty(output.insn, output.output);
        let (_, tys) = <C::I>::rc_for_type(ty).unwrap();
        for ((temp, dst), ty) in temp_regs.by_ref().zip(dsts.regs()).zip(tys) {
            renamer.add_rename(*temp, dst.to_reg(), *ty);
        }
    }
The problem here is that due to the way the Rust zip routine works, the first pass through that loop will already consume both registers in temp_regs (the ValueRegs returned from lower). The second pass through the loop will find temp_regs empty and simply not initialize the second output at all.

This isn't an issue at the moment since the only multi-output instruction currently implemented in ISLE is iadd_ifcout, and here the second output is the carry flag, which is ignored as an output anyway (it's handled differently by explicitly matching the combination of the iadd_ifcout and the carry consumer). But if we want to handle instructions that really use multiple outputs (most notably call instructions), this is a problem.

Now, this specific issue can be fixed by doing the zip the other way around. B.t.w. this then actually breaks iadd_ifcout - the current implementations rely on the second output being dropped! That problem can also be fixed e.g. by special-casing IFLAG type outputs. But even then, we can only handle at most two outputs, because any single ValueRegs contains at most two registers.

How is this supposed to be handled? Should lower be changed to return something like a vector of ValueRegs instead of just a single one? Or should there be a different ISLE constructor for multi-output instructions?

CC @cfallin

Wasmtime GitHub notifications bot (Feb 01 2022 at 18:34):

github-actions[bot] commented on issue #3747:

Subscribe to Label Action

cc @cfallin, @fitzgen

<details>
This issue or pull request has been labeled: "isle"

Thus the following users have been cc'd because of the following labels:

cfallin: isle

fitzgen: isle

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

Wasmtime GitHub notifications bot (Feb 01 2022 at 18:34):

cfallin commented on issue #3747:

Thanks for writing this up -- it's still an unresolved question in the ISLE integration but we've talked about a few approaches -- the main ones that I think are viable exactly those you named in your last paragraph. To expand a bit more:

We could add a lower_2, lower_3, ... entrypoint for those instructions that have a fixed number of results -- the add+carry-like operators, etc. Here we should have a return type that is a container with exactly this many ValueRegs.

We could additionally add a lower_multiple entrypoint for those instructions that return a dynamic (at compiler-backend-author-time) number of values. call and, if we eventually SSA-ify by creating a pseudoinst that grabs argument values, func_args are probably the two most prominent examples. Any others that might fit this?

Specifically I think it's important that we don't change the existing lower entrypoint -- the clarity of just returning one value, without additional wrappers, should remain for most operators I think.

Wasmtime GitHub notifications bot (Feb 01 2022 at 18:36):

fitzgen commented on issue #3747:

Thanks for digging into this.

How is this supposed to be handled? Should lower be changed to return something like a vector of ValueRegs instead of just a single one? Or should there be a different ISLE constructor for multi-output instructions?

I think having a different ISLE constructor for multi-output instructions would strike a good balance here. We want the single-output common case to read nicely, and the more we have to repackage and wrap the result (Reg into ValueRegs into ValuesRegs or something) the more difficult it is to read 99% of the lowerings.

Wasmtime GitHub notifications bot (Feb 02 2022 at 10:34):

uweigand commented on issue #3747:

Hmm. I agree that we shouldn't have to do mass changes of existing back ends. But I don't see how these would be needed just because we change the return type of lower - basically all existing rules for lower return either value_reg, value_regs, or value_regs_none, so as long as we change the return type of those accordingly, the actual written rules wouldn't have to change.

So as an example, we could change the output type of lower to something like ValueRegsList, and then have value_regs_none return an empty ValueRegsList and value_reg and value_regs return a single-element ValueRegsList. We'd probably want a new value_regs_pair or something for the iadd_ifcout case.

For variadic instructions like call we'd need a new mechanism to generate variable-length lists anyway, probably using some sort of builder pattern, starting from an empty list and appending outputs in a matching rule using tail recursion.

Wasmtime GitHub notifications bot (Feb 02 2022 at 14:25):

bjorn3 commented on issue #3747:

Would it be possible to migrate call and ret to ISLE at all? They use quite a lot of non-trivial logic to handle the calling convention.

Wasmtime GitHub notifications bot (Feb 02 2022 at 14:44):

uweigand commented on issue #3747:

Would it be possible to migrate call and ret to ISLE at all? They use quite a lot of non-trivial logic to handle the calling convention.

I believe it is possible. In fact, I have an experimental patch that does so for s390x, and it is working except for functions with multiple return values, which is why I opened this issue.

Once I'm a bit further along with cleaning up the remaining issues, I'd be happy to post a proof-of-concept patch to start further discussion.

Wasmtime GitHub notifications bot (May 04 2022 at 20:02):

cfallin labeled issue #3747:

Support for instructions with multiple outputs in ISLE seems to be missing and/or broken at the moment. In general, CLIF instructions may have any number of outputs, each of which may in turn be implemented as one or more registers (i.e. a ValueRegs structure).

However, with ISLE instruction selection, the lower_common helper routine calls the lower ISLE constructor, which only has a _single_ ValueRegs return value. Now, there is some code in lower_common that seems intended to use the registers provides in that single ValueRegs to implement multiple outputs. But that doesn't appear to be working.

In particular, in the common case where we have two outputs with a single register each, and the ISLE lower constructor attempts to handle this by returning two registers in a single ValueRegs, we run into this loop:
    for output in outputs {
        let dsts = get_output_reg(isle_ctx.lower_ctx, *output);
        let ty = isle_ctx.lower_ctx.output_ty(output.insn, output.output);
        let (_, tys) = <C::I>::rc_for_type(ty).unwrap();
        for ((temp, dst), ty) in temp_regs.by_ref().zip(dsts.regs()).zip(tys) {
            renamer.add_rename(*temp, dst.to_reg(), *ty);
        }
    }
The problem here is that due to the way the Rust zip routine works, the first pass through that loop will already consume both registers in temp_regs (the ValueRegs returned from lower). The second pass through the loop will find temp_regs empty and simply not initialize the second output at all.

This isn't an issue at the moment since the only multi-output instruction currently implemented in ISLE is iadd_ifcout, and here the second output is the carry flag, which is ignored as an output anyway (it's handled differently by explicitly matching the combination of the iadd_ifcout and the carry consumer). But if we want to handle instructions that really use multiple outputs (most notably call instructions), this is a problem.

Now, this specific issue can be fixed by doing the zip the other way around. B.t.w. this then actually breaks iadd_ifcout - the current implementations rely on the second output being dropped! That problem can also be fixed e.g. by special-casing IFLAG type outputs. But even then, we can only handle at most two outputs, because any single ValueRegs contains at most two registers.

How is this supposed to be handled? Should lower be changed to return something like a vector of ValueRegs instead of just a single one? Or should there be a different ISLE constructor for multi-output instructions?

CC @cfallin

Wasmtime GitHub notifications bot (Aug 04 2022 at 20:47):

uweigand closed issue #3747:

Support for instructions with multiple outputs in ISLE seems to be missing and/or broken at the moment. In general, CLIF instructions may have any number of outputs, each of which may in turn be implemented as one or more registers (i.e. a ValueRegs structure).

However, with ISLE instruction selection, the lower_common helper routine calls the lower ISLE constructor, which only has a _single_ ValueRegs return value. Now, there is some code in lower_common that seems intended to use the registers provides in that single ValueRegs to implement multiple outputs. But that doesn't appear to be working.

In particular, in the common case where we have two outputs with a single register each, and the ISLE lower constructor attempts to handle this by returning two registers in a single ValueRegs, we run into this loop:
    for output in outputs {
        let dsts = get_output_reg(isle_ctx.lower_ctx, *output);
        let ty = isle_ctx.lower_ctx.output_ty(output.insn, output.output);
        let (_, tys) = <C::I>::rc_for_type(ty).unwrap();
        for ((temp, dst), ty) in temp_regs.by_ref().zip(dsts.regs()).zip(tys) {
            renamer.add_rename(*temp, dst.to_reg(), *ty);
        }
    }
The problem here is that due to the way the Rust zip routine works, the first pass through that loop will already consume both registers in temp_regs (the ValueRegs returned from lower). The second pass through the loop will find temp_regs empty and simply not initialize the second output at all.

This isn't an issue at the moment since the only multi-output instruction currently implemented in ISLE is iadd_ifcout, and here the second output is the carry flag, which is ignored as an output anyway (it's handled differently by explicitly matching the combination of the iadd_ifcout and the carry consumer). But if we want to handle instructions that really use multiple outputs (most notably call instructions), this is a problem.

Now, this specific issue can be fixed by doing the zip the other way around. B.t.w. this then actually breaks iadd_ifcout - the current implementations rely on the second output being dropped! That problem can also be fixed e.g. by special-casing IFLAG type outputs. But even then, we can only handle at most two outputs, because any single ValueRegs contains at most two registers.

How is this supposed to be handled? Should lower be changed to return something like a vector of ValueRegs instead of just a single one? Or should there be a different ISLE constructor for multi-output instructions?

CC @cfallin

Last updated: Oct 23 2024 at 20:03 UTC