Terminator operators that imply "end"

[AndrewScheidecker]

WebAssembly has several operators that imply that any code following them until the next end or else operator will never be executed: ret, br, br_table, unreachable.

I propose that these operators act as implicit end/else operators. This would imply that they may only occur at the end of a control flow block. The end operator would still be useful as a special-case br operator that targets a fixed depth of 0.

This also makes it clear that else can be eliminated, and that an if operator just needs to be followed by two terminator instructions.

I believe this simplifies code generation, since you don't need to worry about the stack having the right type going into an unreachable end operator. I believe it also simplifies the spec and validation, since it completely avoids the question of how to handle code between these operators and the next end.

[ghost]

There seems to be some merit exploring this. The type validation of dead code does appear to be a problem when relating the wasm code back to a presentation format, and this might help.

Would this mean that end == br 0 except that the branch currently unwinds the values stack?

This might help reduce code size when a block fall through needs to unwind the values stack and end the block with a branch, so it can omit the end in this case.

Then would if with an else be equivalent to block block br_if, and if without an else be equivalent to block br_if?

[ghost]

Correction:

• <cond>, if, <A>, end might then be equivalent to block<0>, <cond>, br_unless 0, <A>, br 0 or block<0>, <cond>, br_unless 0, <A>, end where end == br 0.
• <cond>, if, <A>, else, <B>, end might then be equivalent to block<n>, block<0>, <cond>, br_unless 0, <A>, br 1, <B>, br 0 or block<n>, block<0>, <cond>, br_unless 0, <A>, else, <B>, end where else == br 1.

Perhaps if could be defined as effectively block<0>, <cond>, br_unless, and if-else could require an explicit block<n> around this. This might go some way to addressing the code bloat when adding types to blocks as there would be a short opcode for this common case.

E.g. <cond>, if<n>, <A>, else, <B>, end => block<n>, <cond>, if, <A>, br 1, <B>, br 0 or block<n>, <cond>, if, <A>, else, <B>, end

[AndrewScheidecker]

Would this mean that end == br 0 except that the branch currently unwinds the values stack?

Yes, though with the block signature change, they could be the same: end/br0 could take just the results specified by the block signature from the current stack frame and implicitly drop the rest.

Perhaps if could be defined as effectively block<0>, , br_unless, and if-else could require an explicit block around this.

Yes, since the general if can be implemented with blocks and br_if, it might make sense for if to be a shortcut for compressing the common case. However, I think an if with an else block is still justified for compactness. Here's what the byte stream would look like if you needed to use a block for the else:

block
  signature
<cond>
if
<then>
br
  1
<else>
br0

Vs with an if_else_0 that still has an else, but an implicit () signature:

<cond>
if_else_0
<then>
br0
<else>
br0

I think given the frequency of if, the compactness of the last if_else_0 case is worthwhile.

[sunfishcode]

This proposal makes sense to me. Along with block signatures, this proposal would give us a concrete stack state at every instruction, with no special states or modes. Even if special states or modes are simple today, they require have the potential to interact with future features, and they require extra testing.

One detail: removing else would make it ambiguous whether an if ... end has an "else" arm. A simple way to fix this would be to introduce an if_else opcode, so the two sequences would be:

• if ...end`
• if_else ... end ... end

(and any of the ends could be any one of the terminators). This approach also informs consumers up front whether an "else" arm is present, which one could imagine being useful in some circumstances.

[sunfishcode]

A notable feature of this proposal is that it eliminates the awkward zone between an unconditional branch and the subsequent end while still permitting unreachable code. A producer that knows it may emit unreachable code can start a new block before emitting an unconditional branch, and with block signatures, this creates unreachable code but retains a concrete type sequence on the stack.

[ghost]

@ sunfishcode A producer that knows it may emit unreachable code can start a new block before emitting an unconditional branch ...

Good point, so unreachable code can still be emitted like:

block $l1
  block $l2
    br $l1
  <unreachable code>
end

But would this unreachable code be type validated or not?

[AndrewScheidecker]

block $l1
  block $l2
    br $l1
  <unreachable code>
end

But would this unreachable code be type validated or not?

Yes, it you add explicit signature to the blocks. e.g.:

block $l1 : f32
  block $l2 : i32
    f32.const 1.0
    br $l1
  f32.reinterpret/i32
end

I've been rewriting WAVM to support the binary format + stack machine semantics, and am currently targeting a hypothetical version that has both #765 and this implicit terminator proposal. I'm happy to say that eliminates quite a bit of complexity in the validator since, as @sunfishcode pointed out, it eliminates the possibility of code where the stack is in an unknown state. It moves a little of that complexity to assembling a WAST file, but overall I'm happy with it.

[ghost]

@AndrewScheidecker Out of curiosity, does you experimental design have anything to say on the semantics of the block end? See the discussion in WebAssembly/spec#326 Do you see a need for the block end to be semantically different to br 0?

[AndrewScheidecker]

In my prototype, end and br both implicitly discard superfluous elements on the stack. That's an arbitrary choice though, and the implementation could work either way. But end and br do differ in the case of loop:

loop : i32
  <condition>
  if_else : i32
    br 1
  ;; else (implied by the preceding br)
    i32.const 1
    br 0
  end

There isn't a good way to replace the final end with a br; getting rid of end would mean that you have to wrap a loop in a block to break out of it. loop pushes a single entry on the control stack, but that entry effectively has two branch targets: one that is only used by end, and one that is used by the various br operators. It might be possible to eliminate this distinction, but I haven't thought of a good way yet.

[ghost]

@AndrewScheidecker Was loop going to retain two labels, two blocks?

Perhaps two signatures too, unless the common case is a void result. A loop is an operator that could really benefit from consuming values from the stack at the head of the loop, so could make use of a signature with arguments and results. The exit block signature will be different in general.

A loop end that exits the loop would then be equivalent to br 1, and ending a loop with br 0 would be repeating the loop and perhaps that could be the 'end' now. It's a little different but might even be a more familiar structured control flow operator - a loop that repeats and requires a break to exit from.

btw: might there me merit in if_else being equivalent to the following, but with the condition popped? It would make if_else just a macro. This would differ because the 'then' path could branch to the 'else' path, and it would require the 'then' path to end in br 1 if not falling through to the 'else' path. No sure myself, it would not be so clearly a diamond pattern.

block $l1 : <sig>
  block $l2 : void
    br_unless $l2
    ...

[AndrewScheidecker]

Was loop going to retain two labels, two blocks?

I was under the impression it was going to change to one label, but it looks like it hasn't been merged yet (#710), so perhaps it will keep both labels.

If the branch target stack isn't 1:1 with the control structure stack (e.g. the terminating operator for the loop control structure will implicitly pop two branch targets), then it does seem like end can be replaced with br in all cases.

Perhaps two signatures too, unless the common case is a void result. A loop is an operator that could really benefit from consuming values from the stack at the head of the loop, so could make use of a signature with arguments and results. The exit block signature will be different in general.

I agree that it would be nice, but it needs to be exposed through WAST for it to be useful, so my test just uses signatures with no parameters and an inferred return type.

[ghost]

@AndrewScheidecker If the branch target stack isn't 1:1 with the control structure stack (e.g. the terminating operator for the loop control structure will implicitly pop two branch targets), then it does seem like end can be replaced with br in all cases.

But the end of the loop could be changed to branch to the loop head, and then it seems to all match up.

[AndrewScheidecker]

I converted WAVM to do what I believe the current standard is (unreachable code is allowed between an unconditional branch and the end of the current control structure, and consumers should ignore it), but I recreated the changes proposed in this issue as a single commit for easy diffing: WAVM/WAVM@6d20818

Part of the change is to use distinct opcodes for if with and without an else branch, so you don't need the else opcode to disambiguate the start of the else branch from then end of an else-less if. These changes made my translation to LLVM IR about 5% faster, which I hypothesize is mostly because it no longer needs to speculatively create a basic block for the else branch of an else-less if.

The zipped size savings were about .5%; that's comparing against a WASM that already didn't have any unreachable code that would be disallowed by this change, so it only comes from two changes: the end opcode can be saved when a control structure ends in an unconditional branch, and the else-less if opcode doesn't need a result signature (it cannot yield a result).

[RyanLamansky]

An alternative thought: target index 0 goes to the next instruction. In the case of br_table, this would allow code following this instruction to be used as a target, saving a block layer and its corresponding 3 bytes.

[qwertie]

@Kardax hmm, to me it makes more sense to eliminate the default case, so br_table would be conditional on whether the index is in range.

[RyanLamansky]

@qwertie Assuming that AngryBots13.wasm is a real-world example, target-0-is-next-instruction would save 4194* bytes, but eliminating the default case would only save 1398* as this particular file has no default 0, necessitating the immediate next instruction to be a br. A clever compiler could re-order the blocks so that the default comes first, but this may not be easy or even possible if it's in the middle of a fall-through series**.

All of the options discussed in this issue will save bytes, though, so I think if the binary format is not yet frozen, one of these approaches should be implemented.

(*) Branches targeting what used to be level 127 but is now 128 will grow by 1 byte; I'm not accounting for this currently, but such deep block stacks should be uncommon.
(**) My WASM reader isn't currently sophisticated enough to assess this possibility.

[qwertie]

I have no data in front of me, but thinking about C switches, in the majority of them, default: is preceded by a break, which allows the optimization you mentioned.

I believe omitting br_table's default label would be simpler, both in terms of describing br_table in the spec and in terms of implementation.

Edit: I just realized I don't know what you meant by "this file has no default 0" so I did not actually understand what you said. But I'm Canadian, so, sorry.

[RyanLamansky]

@qwertie AngryBots13.wasm has no instances of br_table where default is 0, so removing the default means the very next instruction after the br_table will be br, which requires two bytes. So, the savings of removing the default isn't that great for this file without the optimization I mentioned.

[pizlonator]

It's too late for this.