Proposals with unmodeled side effects

[tlively]

Recently we have seen a couple proposals that introduce instructions with side effects that are not modeled in the WebAssembly semantics. Specifically, they are:

1. https://github.com/WebAssembly/design/issues/1344, which proposes tracing instructions that are semantically nops but have platform-dependent, unmodeled side effects.

2. https://github.com/WebAssembly/design/issues/1345, which proposed an await instruction that is semantically equivalent to a host call, but had some unmodeled semantic significance in the embedder.

Another similar idea that I have heard (but that has not been proposed anywhere) is to add a debugger instruction that would be similar to the debugger statement in JS. This instruction would also be semantically equivalent to a host call but have some unmodeled significance in the embedder.

These proposals are different from previous proposals because they seek to standardize a behavior that is not modeled in the WebAssembly formal semantics. In other words, they are trying to give WebAssembly the ability to do something without needing to import that functionality from the host and without extending the formal semantics to describe the new behavior.

Each of these proposals would be a better fit with WebAssembly's current design if they relied on some sort of intrinsic imports to provide their new functionality rather than relying on new instructions, but that is not currently possible. The only forum for standardizing imports at the moment is the WASI subgroup, but WASI is too high-level for these proposals and is not meant to be implemented in all WebAssembly engines. Additionally, these proposals don't want to introduce new function calls at runtime, so ideally they would use some sort of compile-time import. Such an idea has also come up in the context of type imports: https://github.com/WebAssembly/proposal-type-imports/issues/6.

I see three paths forward for proposals with unmodeled side effects:

1. We consider them out of scope for WebAssembly. This would be reasonable given WebAssembly's design goals, but it also closes the door on a lot of potentially useful ideas. On the other hand, maybe it is good to close that door more explicitly if the end result would be the same for each individual proposal.

2. We continue to evaluate them on a case-by-case basis and agree that in principle we are fine with having instructions with unmodeled side effects in WebAssembly. It would be good to declare that design principle now to provide clarity to proposal authors. This leaves the door open for all these potentially useful ideas, but sacrifices the purity of the core spec.

3. We develop some framework for standardizing low-level intrinsic imports that are expected to be implemented by all WebAssembly engines, not just WASI engines. The benefit would be that we could maintain the purity of the WebAssembly core semantics while still keeping the door open for less-formally standardized unmodeled behavior. The cost of course is that we would have to figure out how this could work.

Personally, I favor the first option.

[fgmccabe]

Actually, when listening to the discussion about the tracing instructions, I felt that they should be modeled as imports. So, I am also settling on option #1 - ruling them out of scope.

[RossTate]

[Edit: updated after better understanding what each option means] I think option 3 is the right direction, with this functionality being out of core WebAssembly but standardized within the WebAssembly (GitHub) organization and efficient support provided through support for compile-time imports.

To elaborate a bit on the connection to WebAssembly/proposal-type-imports#6, one pattern I suspect would be useful for WebAssembly is for modules to import an abstract type and functions on that type that are instantiated at compile time, rather than instantiation time, so that calls to them can instead be compiled to instruction sequences. For example, a module could import an abstract type representing specifically DOM objects (rather than arbitrary JS objects) and operations for manipulating the DOM, and those operations could be compiled straight to instructions for directly-but-safely accessing DOM objects. This could eventually make WebAssembly the more efficient way to manipulate the DOM.

That's obviously a long way off (and I don't know enough about DOM implementations to know how practical it is), but it's a direction I thought WebAssembly could go, and (option 1 of) this issue in combination with WebAssembly/proposal-type-imports#6 would be first steps in that direction.

[binji]

Additionally, these proposals don't want to introduce new function calls at runtime, so ideally they would use some sort of compile-time import.

I'd like to see the expected function call overhead for these proposals -- that should help us decide. If we go with option 1 now, we're basically saying that the overhead is acceptable.

This leaves the door open for all these potentially useful ideas, but sacrifices the purity of the core spec.

We decided to do this with the alignment field -- we could argue whether that was a good decision, but it's not unprecedented for us to include information in the binary format that isn't needed by the wasm virtual machine.

one pattern I suspect would be useful for WebAssembly is for modules to import an abstract type and functions on that type that are instantiated at compile time, rather than instantiation time, so that calls to them can instead be compiled to instruction sequences.

This sounds more like option 1 now, with option 3 in the future. Or am I misunderstanding your suggestion?

[tlively]

Additionally, these proposals don't want to introduce new function calls at runtime, so ideally they would use some sort of compile-time import.

I'd like to see the expected function call overhead for these proposals -- that should help us decide. If we go with option 1 now, we're basically saying that the overhead is acceptable.

Unless we develop a framework for standardizing functions that must be available as imports, we would not only be saying that it is appropriate to implement the proposed functionality via imports, but we would also be giving up on standardizing the proposed functionality at all.

This leaves the door open for all these potentially useful ideas, but sacrifices the purity of the core spec.

We decided to do this with the alignment field -- we could argue whether that was a good decision, but it's not unprecedented for us to include information in the binary format that isn't needed by the wasm virtual machine.

I'm not sure alignment hints are quite the same as the proposals I'm concerned about, since their only observable behavior is a change in performance. That seems qualitatively different from proposals that explicitly provide information to the embedder or influence its execution in some way besides timing.

[binji]

Unless we develop a framework for standardizing functions that must be available as imports, we would not only be saying that it is appropriate to implement the proposed functionality via imports, but we would also be giving up on standardizing the proposed functionality at all.

Right, and personally I think that might be too strong. I suppose that means I prefer option 3, as long as we are sure we need it (i.e. it's significantly better than using an imported function directly, for one reason or another). It's not too hard to imagine how we'd implement this: by providing a new import descriptor for an intrinsic function which is known to the embedder by name, and not provided in the import list during instantiation. As mentioned in today's CG call, we could model these exactly as we do calls to host function. We could consider optional intrinsics too, so a VM that doesn't support the intrinsic could treat it as a nop.

I'm not sure alignment hints are quite the same as the proposals I'm concerned about, since their only observable behavior is a change in performance.

Right, though tracing + debugging should have no effect on observable behavior either. It doesn't seem so far off to me, but I suppose that's just a difference of opinion.

[fgmccabe]

This reminds me, we have been toying with the idea of macros. Importing a macro sounds potentially like one way to model things like instrumentation and debugging features.

[RossTate]

Sorry, I think I misunderstood the difference between the options. I revised the intro to my comment above to be in line with what I know believe the difference between the options is.

[sunfishcode]

I'm curious about option 3's goal of maintaining the "purity of the WebAssembly core semantics". It would seem that doing so would require thing we call "the WebAssembly core semantics" to become a thing that doesn't describe everything "expected to be implemented by all WebAssembly engines".

Also, there's a lot of discussion about allowing things to be "less formal" here, however all the examples given here seem like they could be expressed within the spec framework. Obviously full semantics for eg. a debugger instruction wouldn't make sense to describe, but the spec already does describe calls to host functions with arbitrary unmodeled non-deterministic side effects, so it doesn't seem like it'd need to do anything that it isn't already doing.

[kripken]

Performance may be a relevant factor here. A debugger instruction doesn't need to be fast, so it could be a call to an import (standardized as in option 3, or not - separate question). But I believe ITT (and maybe Await) needs to be fast so implementing it as an import (standardized or not) may not be good enough (as the VM only sees the imports at link time, after codegen).

I think that's similar to our general rule for wasm instructions about adding them when there is CPU hardware support and where speed matters? That seems to support ITT being a new instruction.

[fgmccabe]

The ITT instructions are not transparent. I think that that is a large reason for some of the pushback here. Semantically, they seem to be very close to function calls.

[binji]

I'm curious about option 3's goal of maintaining the "purity of the WebAssembly core semantics". It would seem that doing so would require thing we call "the WebAssembly core semantics" to become a thing that doesn't describe everything "expected to be implemented by all WebAssembly engines".

I think "purity" is the wrong concept here. I think of it as more of a layering problem. We can specify these instructions in the core spec -- with similar behavior to a host function call. But the problem is that is all that it would be. So now imagine how the core spec would look: we'd have N instructions that all say that the behave exactly as a host function call, as far as core wasm is concerned. The only way to differentiate them is by the external effects. So why are they specified in the core?

This is the reason to want them to be imported functions instead, which I think is a good instinct. The trouble there is that they don't map well there for other reasons: 1) they often need to be compiled directly for performance or otherwise (e.g. ITT) 2) they need host functionality that we otherwise don't want to expose directly (e.g. await).

I think that's a good reason to have a generic "middle ground" where we can specify something that looks like an import, but is more constrained. It's still specified, but perhaps not in the core spec. And then the core spec just needs to describe how to define one of these (i.e. how many immediate bytes, and the stack signature).

[tlively]

I think that's a good reason to have a generic "middle ground" where we can specify something that looks like an import, but is more constrained. It's still specified, but perhaps not in the core spec.

Yes, this is what I was thinking with option 3.

The problem is that if we can formally specify the behavior of the import, we might as well just extend WebAssembly's semantics to describe the new behavior and make it an instruction. Using an import is only useful for things that cannot be feasibly formalized, so the middle ground spec would necessarily be less formal.

Having a less-formal spec layered on top of the core spec that we still expect all engines to implement seems undesirable, so I'd rather go with option 1 and simply consider unmodeled side effects out of scope for standardization by the WebAssembly CG (except via WASI).

[binji]

The problem is that if we can formally specify the behavior of the import, we might as well just extend WebAssembly's semantics to describe the new behavior and make it an instruction.

Maybe, though having a generic mechanism would have other benefits too:

1) They don't take up opcode space 2) They are forward compatible (e.g. you can decode/validate them without understanding them) 3) It's possible to make them optional 4) They can be specified without involving the a lot of core spec (avoiding a lot of unnecessary detail), and could potentially be handled by a separate group (similar to WASI)

Having a less-formal spec layered on top of the core spec that we still expect all engines to implement seems undesirable

I don't know that we should expect all engines to implement these. At least for ITT and debugger, it would be reasonable for an engine to ignore those operations entirely. And as @sunfishcode mentioned above, they would be less-formal only in the additional non-core behavior. As far as the core is concerned, the behavior can be modeled formally.

[taralx]

We already have a mechanism for ignored information: custom sections. What if this information were stored there, with e.g. some kind of code pointer?

[binji]

@taralx It may be possible to use the custom section to do that (at least for ITT and debugging, not sure if it works well for await). However, currently custom sections are completely unstructured, so tools really can't make any assumption about the contents, and generally must discard them. This would be an argument for having a specified, well-known structure for annotating the binary format (there was some previous discussion here about that). If we went this route, we'd want to be careful not to break streaming compilers -- so the annotation custom section probably needs to occur before the code section.

It's also not a perfect fit -- these instructions aren't really annotations on existing instructions, they are meant to be instructions themselves. We could encode them as nop in the instruction stream, and annotate those, but that doesn't match the semantics we were describing above (e.g. equivalent to a host function call). The custom section could mark an insertion point instead, but that seems somewhat awkward from a code generation standpoint.

[sunfishcode]

They don't take up opcode space

With eg. the 0xfc "miscellaneous" prefix, new instructions wouldn't take up significant opcode space either.

They are forward compatible (e.g. you can decode/validate them without understanding them)

That's true, though you wouldn't be able to instantiate them without a polyfill. And in general it's not something wasm has worried about when adding features.

It's possible to make them optional

If we mean "a VM that doesn't support the intrinsic could treat it as a nop", then it sounds like we'd still be expecting all VMs to recognize these features, even if the normative requirements permit implementing them as nops.

The only way to differentiate them is by the external effects. So why are they specified in the core?

They'd be differentiated by non-normative wording. A reason to put them in core would be that the core spec is the spec that all engines would be expected to recognize them, and the core spec is where we put things that are expected of all engines.

Is there an assumption that the core spec shouldn't have non-normative wording?

[rwinterton]

The trace instruction should be inlined in my opinion. Treating as a function seems like it could add more security risks but I am not a security expert. The question of the trace instruction maybe reordered by the compiler was brought up as a concern in the discussion. Practically as long as the instruction is not moved out of a block of code or moved into a block of code or loop it wouldn't matter for traces. Moving in and out of blocks or loops is a problem. Preferably it would not be move for the user but it is easy to see if it is, just not convenient. From the uArchitecture perspective instructions are reordered all the time analogous to the release compiler reorder and we don't always expect to always see instructions executed ordered. Pertaining to this issue I think proposal 1 or 3 would work but I prefer 3.

[lukewagner]

Considering the three hypothetical use cases of (1) ITT, (2) await, (3) a debugger instruction, I think each is actually subtly different from a core spec POV:

1. with ITT, the core spec can normatively specify that the state of the store is not modified by execution of ITT instructions, the strongest guarantee.
2. with await, the core spec could assert that the only modifications to the store possible are those performed by reentrant execution of exports or arbitrary modification to imported/exported mutable state (memories, tables, globals), which allows a module to ensure some high-level invariants.
3. with debugger, the core spec could only assert basic well-formedness was maintained using the same language that the spec currently uses for host functions (because, in general, the debugger is all-powerful and can, e.g., modify arbitrary encapsulated local state)

To me, this is an argument for considering each of these on a case-by-case basis as core wasm instructions and not lumping them together from a core spec pov.

[binji]

This topic came up again in today's GC subgroup meeting, where @tebbi presented on JS and wasm GC interop. There was an example of an instruction that modified a "Run-time type" (RTT) (see https://github.com/WebAssembly/gc/blob/master/proposals/gc/MVP.md#runtime) to add information about how JS would interact with it. Again, these instructions would have no affect on Wasm behavior, and could potentially be modeled as a compile-time function instead. There was some concern that these could be "constant instructions", so they could be used as global initializers, so perhaps being modeled as a function call wouldn't be quite right either.

[rossberg]

We could relax the call restriction in initialisers, e.g., by only allowing calling imported functions, similar to how we only allow reading imported globals. That seems natural, even more so when limited to compile-time imports, distinguishing which will require explicit annotations anyway.

[tebbi]

I agree that more flexibility for initialisers would address most issues (except for the fact that there is no catch-all type for RTTs, which would be necessary to pass an RTT to an imported function). This will introduce arbitrary side effects for global initialisers though, so the execution order becomes observable. Specifying something like execution on first access to the global could make sense for startup.

[tlively]

1363 is another proposal that might introduce a semantic no-op instruction. Specifically, it proposes using instructions to encode branch probability hints.

[tlively]

And another new one! #1364 proposes adding prefetch instructions.

I have to say I am coming around to the idea of adding nop instructions with unmodeled side effects to the core spec, given the wide variety of useful things folks have proposed doing with them.

[RossTate]

I think #1363 and #1364 are a bit different than the other examples. They are both performance hints. In the case of #1363, it cannot in general be modeled by a function call. In both cases, the side effect is restricted to timing behavior. In both cases, you could remove an operation and no one inside or outside of WebAssembly could tell the difference (unless you're doing something very low level like monitoring caches). On the other hand, removing an operation for #1344 would be externally visible. So while they're certainly similar, I think performance hints are different enough that they'd likely be better served by a different solution.